[go: up one dir, main page]

TWI777231B - 向量內積計算裝置 - Google Patents

向量內積計算裝置 Download PDF

Info

Publication number
TWI777231B
TWI777231B TW109129650A TW109129650A TWI777231B TW I777231 B TWI777231 B TW I777231B TW 109129650 A TW109129650 A TW 109129650A TW 109129650 A TW109129650 A TW 109129650A TW I777231 B TWI777231 B TW I777231B
Authority
TW
Taiwan
Prior art keywords
vector
data
accumulator
vector data
inner product
Prior art date
Application number
TW109129650A
Other languages
English (en)
Other versions
TW202209136A (zh
Inventor
林泰吉
Original Assignee
國立中正大學
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 國立中正大學 filed Critical 國立中正大學
Priority to TW109129650A priority Critical patent/TWI777231B/zh
Priority to US17/076,548 priority patent/US11500964B2/en
Publication of TW202209136A publication Critical patent/TW202209136A/zh
Application granted granted Critical
Publication of TWI777231B publication Critical patent/TWI777231B/zh

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation
    • G06F7/5443—Sum of products
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/50—Adding; Subtracting
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/38—Indexing scheme relating to groups G06F7/38 - G06F7/575
    • G06F2207/48—Indexing scheme relating to groups G06F7/48 - G06F7/575
    • G06F2207/4802—Special implementations
    • G06F2207/4814—Non-logic devices, e.g. operational amplifiers
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F5/01—Methods or arrangements for data conversion without changing the order or content of the data handled for shifting, e.g. justifying, scaling, normalising
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/527—Multiplying only in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel
    • G06F7/5272—Multiplying only in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel with row wise addition of partial products
    • G06F7/5275—Multiplying only in serial-parallel fashion, i.e. one operand being entered serially and the other in parallel with row wise addition of partial products using carry save adders
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • General Engineering & Computer Science (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (AREA)
  • Algebra (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Container Filling Or Packaging Operations (AREA)
  • Length Measuring Devices By Optical Means (AREA)
  • Supplying Of Containers To The Packaging Station (AREA)
  • Complex Calculations (AREA)

Abstract

本發明係揭露一種向量內積計算裝置，包含一向量資料排列器、一向量資料前累加器、一數字轉換器與一後累加器。向量資料排列器儲存第一向量，並據此依序輸出複數個向量資料。向量資料前累加器儲存第二向量，並接收每一向量資料，以據此對第二向量進行前累加，進而產生複數個累加結果。數字轉換器與後累加器接收每一向量資料對應之所有累加結果，並將其進行對應處理，以產生一內積值。本發明利用向量資料前累加器及數字轉換器實現查表記憶體，以提升計算速度及降低功耗。

Description

向量內積計算裝置
本發明係關於一種計算裝置，且特別關於一種向量內積計算裝置。
分散式算數(distributed arithmetic)是訊號處理硬體架構設計上，以查表記憶體取代向量內積(inner product)中大量乘加(multiply-accumulation,MAC)計算的技巧。但查表記憶體會隨著向量長度以指數形式快速增長，故其僅適用於短向量內積計算。
公式(1)表示向量x與h的內積計算，其中向量x與h的長度皆為K，向量x與h的字長皆為N位元，向量x包含複數個第一子向量，xi為第i個第一子向量，向量h包含複數個第二子向量，hi為第i個第二子向量。經由K個N位元的乘法得到複數個乘積，經由K-1個加法將上述乘積加起來，則得到向量x與h的內積值y。換句話說，內積值y需要K個乘加計算而得到。假設x是無號數，則子向量xi則表示為x i,j ．2 j ，其中j為次方數。因為向量h與j無關，故可交換兩個累加運算的位置，以得到公式(1)之最後的數學式，此即分散式算數的基本原理。因為括號內為N位元的h向量與向量xi,j內積，其中向量xi,j為[x0,j,x1,j,...,xK-1,j]，所以根 據長度為K的向量xi,j的實際值，總共只有2K種結果，將此2K種結果先計算完成儲存在有2K個條目(entry)的記憶體中，括號內的計算可直接查詢記憶體來完成，括號外的計算等同為序列乘法器進行移位累加運算。第1圖為先前技術之分散式 算數之硬體架構示意圖。此硬體架構包含基於移位暫存器之資料產生器10，資料產生器10將子向量xi轉換成位元層次(bit-level)的向量xi,j，依序在查表記憶體12中查詢2K個條目。舉例來說，如表一所示，當向量xi,j為[000...0]時，查表記憶體12對應的條目為0。當向量xi,j為[000...1]時，查表記憶體12對應的條目為h1。當向量xi,j為[111...1]時，查表記憶體12對應的條目為所有hi的總和。經過N次在查表記憶體12中查詢條目及移位累加器14進行N次的運算後可完成內積值y。查表記憶體12是分散式算數架構最關鍵的元件，查表記憶體12之大小隨著向量長度以指數形式快速增長，故僅適用於短向量內積計算。傳統上長向量內積需要以數個查表分段查詢，失去分散式算數原先的優勢。
Figure 109129650-A0305-02-0004-1
Figure 109129650-A0305-02-0004-3
因此，本發明係在針對上述的困擾，提出一種向量內積計算裝置，以解決習知所產生的問題。
本發明提供一種向量內積計算裝置，其係適用於長向量內積計算，大幅降低計算量，同時提升計算速度及降低功耗。
在本發明之一實施例中，提供一種向量內積計算裝置，其包含一向量資料排列器(vector data arranger)、一向量資料前累加器(vector data pre-accumulator)、一數字轉換器與一後累加器(post-accumulator)。向量資料排列器用於儲存。向量資料前累加器包括平行設置之複數條字元線，所有字元線連接向量資料排列器，其中向量資料前累加器用於儲存向量內積計算之一第二向量，所有字元線用於接收每一向量資料，每一向量資料致能字元線，以根據被致能之字元線對第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果。數字轉換器連接向量資料前累加器，其中數字轉換器用於接收每一向量資料對應之所有累加結果，並將其移位相加，以得到數字形式之一總資料值。後累加器連接數字轉換器，其中後累加器用於接收所有向量資料對應之總資料值，並對所有向量資料對應之總資料值進行移位累加，以產生一內積值。
在本發明之一實施例中，向量資料前累加器更包括複數個記憶胞與平行設置之複數條位元線，第二向量包含複數個資料字元向量，每一字元線透過記憶胞連接所有位元線，其中分別對應所有字元線之所有記憶胞分別用於儲存所有資料字元向量，向量資料前累加器用於累加對應被致能之字元線的所有位元線所對應之資料字元向量，進而產生分別對應所有位元線之所有累加結果。
在本發明之一實施例中，數字轉換器為冗餘轉二補數(redundant to 2's complement,RTC)轉換器，數字形式為二補數形式。
在本發明之一實施例中，後累加器根據
Figure 109129650-A0305-02-0005-5
對所有向量資料對應之總資料值進行移位累加，以產生內積值，P為內積值，N為所有向量資料之總數量，Tj為第j個向量資料對應之總資料值。
在本發明之一實施例中，向量資料前累加器為一記憶體內運算架構(computing-in-memory architecture)。
在本發明之一實施例中，資料字元向量包含邏輯”1”或邏輯”0”。
在本發明之一實施例中，向量資料前累加器產生之每一累加結果為其對應之邏輯”1”的總數目。
在本發明之一實施例中，數字轉換器與後累加器整合為一進位保留加法器(carry-save adder)。
在本發明之一實施例中，提供一種向量內積計算裝置，其包含一向量資料排列器(vector data arranger)、一向量資料前累加器(vector data pre-accumulator)、一後累加器(post-accumulator)與一數字轉換器。向量資料排列器用於儲存向量內積計算之一第一向量，第一向量包含複數個子向量，向量資料排列器用於依序輸出複數個向量資料，其中每一向量資料包含每一子向量之至少一相同位元。向量資料前累加器包括平行設置之複數條字元線，所有字元線連接向量資料排列器，其中向量資料前累加器用於儲存向量內積計算之一第二向量，所有字元線用於接收每一向量資料，每一向量資料致能字元線，以根據被致能之字元線對第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果。後累加器連接向量資料前累加器，其中後累加器用於接收所有向量資料對應之所有累加結果，並將其移位累加，以得到冗餘形式之複數個累加資料值。數字轉換器連接後累加器，其中數字轉換器用於接收所有累加資料值，並將其移位相加，以得到數字形式之一內積值。
在本發明之一實施例中，向量資料前累加器更包括複數個記憶胞與平行設置之複數條位元線，第二向量包含複數個資料字元向量，每一字元線透過記憶胞連接所有位元線，其中分別對應所有字元線之所有記憶胞分別用 於儲存所有資料字元向量。向量資料前累加器用於累加對應被致能之字元線的所有位元線所對應之資料字元向量，進而產生分別對應所有位元線之所有累加結果。
在本發明之一實施例中，數字轉換器為冗餘轉二補數(redundant to 2's complement,RTC)轉換器，數字形式為二補數形式。
在本發明之一實施例中，向量資料前累加器為一記憶體內運算架構(computing-in-memory architecture)。
在本發明之一實施例中，資料字元向量包含邏輯”1”或邏輯”0”。
在本發明之一實施例中，向量資料前累加器產生之每一累加結果為其對應之邏輯”1”的總數目。
在本發明之一實施例中，數字轉換器與後累加器整合為一進位保留加法器(carry-save adder)。
在本發明之一實施例中，數字轉換器根據
Figure 109129650-A0305-02-0007-14
對所有累加資料值進行移位相加，以產生內積值，P為內積值，N為所有向量資料之總數量，ADj為第j個累加資料值，M為每一向量資料對應之所有累加結果之總數量。
基於上述，本發明之實施例感測多條字元線與多條位元線，以利用向量資料前累加器及數字轉換器實現查表記憶體，其中向量資料前累加器之記憶量隨著向量長度線性成長，故適用於長向量內積計算，大幅降低計算量，同時提升計算速度及降低功耗。
茲為使 貴審查委員對本發明的結構特徵及所達成的功效更有進一步的瞭解與認識，謹佐以較佳的實施例圖及配合詳細的說明，說明如後：
10:資料產生器
12:查表記憶體
14:移位累加器
20:向量內積計算裝置
201:向量資料排列器
202:向量資料前累加器
2021:字元線
2022:位元線
2023:記憶體陣列
203:數字轉換器
204:後累加器
30:向量內積計算裝置
301:向量資料排列器
302:向量資料前累加器
3021:字元線
3022:位元線
3023:記憶體陣列
303:後累加器
304:數字轉換器
h1~hk:資料字元向量
R:累加結果
T:總資料值
P:內積值
AD:累加資料值
第1圖為先前技術之分散式算數之硬體架構示意圖。
第2圖為本發明之向量內積計算裝置之第一實施例之方塊圖。
第3圖為本發明之向量內積計算裝置之第二實施例之方塊圖。
本發明之實施例將藉由下文配合相關圖式進一步加以解說。盡可能的，於圖式與說明書中，相同標號係代表相同或相似構件。於圖式中，基於簡化與方便標示，形狀與厚度可能經過誇大表示。可以理解的是，未特別顯示於圖式中或描述於說明書中之元件，為所屬技術領域中具有通常技術者所知之形態。本領域之通常技術者可依據本發明之內容而進行多種之改變與修改。
在說明書及申請專利範圍中使用了某些詞彙來指稱特定的元件。然而，所屬技術領域中具有通常知識者應可理解，同樣的元件可能會用不同的名詞來稱呼。說明書及申請專利範圍並不以名稱的差異做為區分元件的方式，而是以元件在功能上的差異來做為區分的基準。在說明書及申請專利範圍所提及的「包含」為開放式的用語，故應解釋成「包含但不限定於」。另外，「耦接」在此包含任何直接及間接的連接手段。因此，若文中描述第一元件耦接於第二元件，則代表第一元件可通過電性連接或無線傳輸、光學傳輸等信號連接方式而直接地連接於第二元件，或者通過其他元件或連接手段間接地電性或信號連接至該第二元件。
於下文中關於“一個實施例”或“一實施例”之描述係指關於至少一實施例內所相關連之一特定元件、結構或特徵。因此，於下文中多處所出現之“一個實施例”或“一實施例”之多個描述並非針對同一實施例。再者，於一或 多個實施例中之特定構件、結構與特徵可依照一適當方式而結合。
除非特別說明，一些條件句或字詞，例如「可以(can)」、「可能(could)」、「也許(might)」，或「可(may)」，通常是試圖表達本案實施例具有，但是也可以解釋成可能不需要的特徵、元件，或步驟。在其他實施例中，這些特徵、元件，或步驟可能是不需要的。
第2圖為本發明之向量內積計算裝置之第一實施例之方塊圖。請參閱第2圖，以下介紹本發明之向量內積計算裝置之第一實施例。向量內積計算裝置20包含一向量資料排列器(vector data arranger)201、一向量資料前累加器(vector data pre-accumulator)202、一數字轉換器203與一後累加器(post-accumulator)204。向量資料排列器201用於儲存向量內積計算之一第一向量，第一向量包含複數個子向量，所有子向量的總數量為K，每一子向量具有N個位元。向量資料排列器201用於依序輸出複數個向量資料，其中每一向量資料包含每一子向量之至少一相同位元或一相同位元組。舉例來說，第一向量包含三個子向量，每一個子向量包含三個位元或三個位元組，向量資料排列器201用於依序輸出三個向量資料。若第一個子向量為[000]，第二個子向量為[010]，第三個子向量為[100]，則第一個向量資料包含每一子向量之第一個位元，即[000]。第二個向量資料包含每一子向量之第二個位元，即[010]。第三個向量資料包含每一子向量之第三個位元，即[001]。在第一實施例中，所有向量資料的總數量有N/B個，其中B為每一向量資料之對應一子向量之相同位元之數量，每個向量資料具有K個位元，其中N與K皆為自然數。向量資料前累加器202包括平行設置之複數條字元線2021，字元線2021的數量為K條，所有字元線2021連接向量資料排列器201，其中向量資料前累加器202用於儲存向量內積計算之一第二向量，所有字元線2021用於接收每一向量資料，每一 向量資料致能字元線2021，以根據被致能之字元線2021對第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果R。數字轉換器203連接向量資料前累加器202，其中數字轉換器203用於接收每一向量資料對應之所有累加結果R，並將其移位相加，以得到數字形式之一總資料值T。後累加器204連接數字轉換器203，其中後累加器204用於接收所有向量資料對應之總資料值T，並對所有向量資料對應之總資料值T進行移位累加，以產生一內積值P。舉例來說，數字轉換器203可為冗餘轉二補數(redundant to 2's complement,RTC)轉換器，數字形式可為二補數形式。後累加器204可根據
Figure 109129650-A0305-02-0010-9
對所有向量資料對應之總資料值T進行移位累加，以產生內積值P，Tj為第j個向量資料對應之總資料值T。此外，數字轉換器203與後累加器204可整合為一進位保留加法器(carry-save adder)，以減少計算延遲與實現成本。
在本發明之某些實施例中，向量資料前累加器202更可包括平行設置之平行設置之複數條位元線2022與一記憶體陣列2023，其中記憶體陣列2023包括複數個記憶胞，第二向量包含複數個資料字元向量h1、h2、...、hk。舉例來說，向量資料前累加器202可為一記憶體內運算架構(computing-in-memory architecture)。位元線2022的數量為M條。每一字元線2021透過記憶胞連接所有位元線2022，其中分別對應所有字元線2021之所有記憶胞分別用於儲存所有資料字元向量h1、h2、...、hk。舉例來說，由上而下之字元線2021分別作為第一字元線、第二字元線、...、第K字元線，則第一字元線連接的記憶胞用於儲存資料字元向量h1，第二字元線連接的記憶胞用於儲存資料字元向量h2，第K字元線連接的記憶胞用於儲存資料字元向量hk。在先前技術中，記憶體陣列一次致能一條字元線，但向量資料前累加器202可以一次致能多條字 元線2021。向量資料前累加器202用於累加對應被致能之字元線2021的所有位元線2022所對應之資料字元向量h1、h2、...、hk，進而產生分別對應所有位元線2022之所有累加結果R。在第一實施例，資料字元向量h1、h2、...、hk包含邏輯”1”或邏輯”0”，所有資料字元向量h1、h2、...、hk為K個，每個資料字元向量h1、h2、...、hk為M位元，每一向量資料對應之所有累加結果R的總數量為M個，M為自然數，每個累加結果R的長度為log2(K+1)位元。在本發明之一實施例中，向量資料前累加器202產生之每一累加結果R可為其對應之邏輯”1”的總數目，但本發明不限於此。因此，向量內積計算裝置20能感測多條字元線2021與多條位元線2022，以利用向量資料前累加器202及數字轉換器203實現查表記憶體，其中向量資料前累加器202之記憶量隨著向量長度線性成長，故適用於長向量內積計算，大幅降低計算量，同時提升計算速度及降低功耗。
假設N等於3，K等於4，則向量資料排列器201依序輸出第一向量資料、第二向量資料與第三向量資料，當向量資料排列器201輸出第一向量資料時，j等於0，當向量資料排列器201輸出第二向量資料時，j等於1，當向量資料排列器201輸出第三向量資料時，j等於2，累加結果R可為第一累加結果、第二累加結果或第三累加結果。
當第一向量資料為[0001]時，向量資料前累加器202接收第一向量資料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第一累加結果，所有第一累加結果等效於h1。數字轉換器203接收所有第一累加結果，並將其移位相加，以得到T0。當第二向量資料為[0011]時，向量資料前累加器202接收第二向量資料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第二累加結果，所有第二累加結果等效於h1+h2。數字轉換器203接收所有第二累加結果，並將其移位相加，以得到T1。當第三向量資料為[1111]時，向量資料前累加器202接收第三向量資 料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第三累加結果，所有第三累加結果等效於h1+h2+h3+h4。數字轉換器203接收所有第三累加結果，並將其移位相加，以得到T2。最後，後累加器204根據
Figure 109129650-A0305-02-0012-10
對T0、T1與T2進行移位累加，以產生內積值P。
第3圖為本發明之向量內積計算裝置之第二實施例之方塊圖。請參閱第3圖，以下介紹本發明之向量內積計算裝置之第二實施例。向量內積計算裝置30包含一向量資料排列器(vector data arranger)301、一向量資料前累加器(vector data pre-accumulator)302、一後累加器(post-accumulator)303與一數字轉換器304。向量資料排列器301用於儲存向量內積計算之一第一向量，第一向量包含複數個子向量，所有子向量的總數量為K，每一子向量具有N個位元。向量資料排列器301用於依序輸出複數個向量資料，其中每一向量資料包含每一子向量之至少一相同位元或一相同位元組。舉例來說，第一向量包含三個子向量，每一個子向量包含三個位元或三個位元組，向量資料排列器301用於依序輸出三個向量資料。若第一個子向量為[000]，第二個子向量為[010]，第三個子向量為[100]，則第一個向量資料包含每一子向量之第一個位元，即[000]。第二個向量資料包含每一子向量之第二個位元，即[010]。第三個向量資料包含每一子向量之第三個位元，即[001]。在第二實施例中，所有向量資料的總數量有N/B個，其中B為每一向量資料之對應一子向量之相同位元之數量，每個向量資料具有K個位元，其中N與K皆為自然數。向量資料前累加器302包括平行設置之複數條字元線3021，字元線3021的數量為K條，所有字元線3021連接向量資料排列器301，其中向量資料前累加器302用於儲存向量內積計算之一第二向量，所有字元線3021用於接收每一向量資料，每一 向量資料致能字元線3021，以根據被致能之字元線3021對第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果R。後累加器303連接向量資料前累加器302，其中後累加器303用於接收所有向量資料對應之所有累加結果R，並將其移位累加，以得到冗餘形式之複數個累加資料值AD。數字轉換器304連接後累加器303。數字轉換器304用於接收所有累加資料值AD，並將其移位相加，以得到數字形式之一內積值P。舉例來說，數字轉換器304可為冗餘轉二補數(redundant to 2's complement,RTC)轉換器，數字形式可為二補數形式。數字轉換器304可根據
Figure 109129650-A0305-02-0013-11
對所有累加資料值AD進行移位相加，以產生內積值P，ADj為第j個累加資料值AD，M為每一向量資料對應之所有累加結果R之總數量。由於累加結果R先以冗餘形式累加，再轉換為二補數形式，所以數字轉換器304的計算次數及相對功耗可以降低，以提升硬體操作速度。此外，數字轉換器304與後累加器303可整合為一進位保留加法器(carry-save adder)，以減少計算延遲與實現成本。
在本發明之某些實施例中，向量資料前累加器302更可包括平行設置之平行設置之複數條位元線3022與一記憶體陣列3023，其中記憶體陣列3023包括複數個記憶胞，第二向量包含複數個資料字元向量h1、h2、...、hk。舉例來說，向量資料前累加器302可為一記憶體內運算架構(computing-in-memory architecture)。位元線3022的數量為M條。每一字元線3021透過記憶胞連接所有位元線3022，其中分別對應所有字元線3021之所有記憶胞分別用於儲存所有資料字元向量h1、h2、...、hk。舉例來說，由上而下之字元線3021分別作為第一字元線、第二字元線、...、第K字元線，則第一字元線連接的記憶胞用於儲存資料字元向量h1，第二字元線連接的記憶胞用於儲存資料字 元向量h2，第K字元線連接的記憶胞用於儲存資料字元向量hk。與第一實施例相同，向量資料前累加器302可以一次致能多條字元線3021。向量資料前累加器302用於累加對應被致能之字元線3021的所有位元線3022所對應之資料字元向量h1、h2、...、hk，進而產生分別對應所有位元線3022之所有累加結果R。在第二實施例，資料字元向量h1、h2、...、hk包含邏輯”1”或邏輯”0”，所有資料字元向量h1、h2、...、hk為K個，每個資料字元向量h1、h2、...、hk為M位元，每一向量資料對應之所有累加結果R的數量為M個，M為自然數，每個累加結果R的長度為log2(K+1)位元。在本發明之一實施例中，向量資料前累加器302產生之每一累加結果R可為其對應之邏輯”1”的總數目，但本發明不限於此。因此，向量內積計算裝置30能感測多條字元線3021與多條位元線3022，以利用向量資料前累加器302及數字轉換器304實現查表記憶體，其中向量資料前累加器302之記憶量隨著向量長度線性成長，故適用於長向量內積計算，大幅降低計算量，同時提升計算速度及降低功耗。
假設N等於3，K等於4，M等於3，則向量資料排列器301依序輸出第一向量資料、第二向量資料與第三向量資料。此外，假設h1為[001]，h2為[010]，h3為[011]，h4為[100]。
當第一向量資料為[0001]時，向量資料前累加器302接收第一向量資料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第一累加結果R，所有第一累加結果R等效於h1。當第二向量資料為[0011]時，向量資料前累加器302接收第二向量資料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第二累加結果R，所有第二累加結果R等效於h1+h2，即[011]。當第三向量資料為[1111]時，向量資料前累加器302接收第三向量資料，以據此對資料字元向量h1、h2、h3與h4進行前累加，進而產生複數個第三累加結果R，所有第三累加結果R等效於h1+h2+h3+h4，即 [022]。後累加器303接收所有第一累加結果R、所有第二累加結果R與所有第三累加結果R，並將其移位累加，以得到冗餘形式之複數個累加資料值AD0、AD1、AD2、AD3與AD4。如公式(2)所示，AD0為1，AD1為1，AD2為3，AD3為2，AD4為0。最後，數字轉換器304根據
Figure 109129650-A0305-02-0015-13
ADj．2j對AD0、AD1、AD2、AD3與AD4進行移位相加，以產生內積值P。
[--001]+[-0110]+[02200]=[02311] (2)
根據上述實施例，向量內積計算裝置感測多條字元線與多條位元線，以利用向量資料前累加器及數字轉換器實現查表記憶體，其中向量資料前累加器之記憶量隨著向量長度線性成長，故適用於長向量內積計算，大幅降低計算量，同時提升計算速度及降低功耗。
以上所述者，僅為本發明一較佳實施例而已，並非用來限定本發明實施之範圍，故舉凡依本發明申請專利範圍所述之形狀、構造、特徵及精神所為之均等變化與修飾，均應包括於本發明之申請專利範圍內。
20:向量內積計算裝置
201:向量資料排列器
202:向量資料前累加器
2021:字元線
2022:位元線
2023:記憶體
203:數字轉換器
204:後累加器
h1~hk:資料字元向量
R:累加結果
T:總資料值
P:內積值

Claims (16)

  1. 一種向量內積計算裝置，包含： 一向量資料排列器(vector data arranger)，用於儲存向量內積計算之一第一向量，該第一向量包含複數個子向量，該向量資料排列器用於依序輸出複數個向量資料，其中每一該向量資料包含每一該子向量之至少一相同位元； 一向量資料前累加器(vector data pre-accumulator)，包括平行設置之複數條字元線，該些字元線連接該向量資料排列器，其中該向量資料前累加器用於儲存向量內積計算之一第二向量，該些字元線用於接收每一該向量資料，每一該向量資料致能該字元線，以根據被致能之該字元線對該第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果； 一數字轉換器，連接該向量資料前累加器，其中該數字轉換器用於接收每一該向量資料對應之該些累加結果，並將其移位相加，以得到數字形式之一總資料值；以及 一後累加器(post-accumulator)，連接該數字轉換器，其中該後累加器用於接收該些向量資料對應之該總資料值，並對該些向量資料對應之該總資料值進行移位累加，以產生一內積值。
  2. 如請求項1所述之向量內積計算裝置，其中該向量資料前累加器更包括複數個記憶胞與平行設置之複數條位元線，該第二向量包含複數個資料字元向量，每一該字元線透過該記憶胞連接該些位元線，其中分別對應該些字元線之該些記憶胞分別用於儲存該些資料字元向量，該向量資料前累加器用於累加對應被致能之該字元線的該些位元線所對應之該資料字元向量，進而產生分別對應該些位元線之該些累加結果。
  3. 如請求項1所述之向量內積計算裝置，其中該數字轉換器為冗餘轉二補數(redundant to 2's complement, RTC) 轉換器，該數字形式為二補數形式。
  4. 如請求項3所述之向量內積計算裝置，其中該後累加器根據
    Figure 03_image027
    對該些向量資料對應之該總資料值進行移位累加，以產生該內積值，P為該內積值，N為該些向量資料之總數量，
    Figure 03_image029
    為第j個該向量資料對應之該總資料值。
  5. 如請求項1所述之向量內積計算裝置，其中該向量資料前累加器為一記憶體內運算架構（computing-in-memory architecture）。
  6. 如請求項1所述之向量內積計算裝置，其中該資料字元向量包含邏輯”1”或邏輯”0”。
  7. 如請求項6所述之向量內積計算裝置，其中該向量資料前累加器產生之每一該累加結果為其對應之該邏輯”1”的總數目。
  8. 如請求項1所述之向量內積計算裝置，其中該數字轉換器與該後累加器整合為一進位保留加法器(carry-save adder)。
  9. 一種向量內積計算裝置，包含： 一向量資料排列器(vector data arranger)，用於儲存向量內積計算之一第一向量，該第一向量包含複數個子向量，該向量資料排列器用於依序輸出複數個向量資料，其中每一該向量資料包含每一該子向量之至少一相同位元； 一向量資料前累加器(vector data pre-accumulator)，包括平行設置之複數條字元線，該些字元線連接該向量資料排列器，其中該向量資料前累加器用於儲存向量內積計算之一第二向量，該些字元線用於接收每一該向量資料，每一該向量資料致能該字元線，以根據被致能之該字元線對該第二向量進行前累加(pre-accumulate)，進而產生複數個累加結果； 一後累加器(post-accumulator)，連接該向量資料前累加器，其中該後累加器用於接收該些向量資料對應之該些累加結果，並將其移位累加，以得到冗餘形式之複數個累加資料值；以及 一數字轉換器，連接該後累加器，其中該數字轉換器用於接收該些累加資料值，並將其移位相加，以得到數字形式之一內積值。
  10. 如請求項9所述之向量內積計算裝置，其中該向量資料前累加器更包括複數個記憶胞與平行設置之複數條位元線，該第二向量包含複數個資料字元向量，每一該字元線透過該記憶胞連接該些位元線，其中分別對應該些字元線之該些記憶胞分別用於儲存該些資料字元向量，該向量資料前累加器用於累加對應被致能之該字元線的該些位元線所對應之該資料字元向量，進而產生分別對應該些位元線之該些累加結果。
  11. 如請求項9所述之向量內積計算裝置，其中該數字轉換器為冗餘轉二補數(redundant to 2's complement, RTC) 轉換器，該數字形式為二補數形式。
  12. 如請求項11所述之向量內積計算裝置，其中該數字轉換器根據
    Figure 03_image047
    對該些累加資料值進行移位相加，以產生該內積值，P為該內積值，N為該些向量資料之總數量，
    Figure 03_image048
    為第j個該累加資料值，M為每一該向量資料對應之該些累加結果之總數量。
  13. 如請求項9所述之向量內積計算裝置，其中該向量資料前累加器為一記憶體內運算架構（computing-in-memory architecture）。
  14. 如請求項9所述之向量內積計算裝置，其中該資料字元向量包含邏輯”1”或邏輯”0”。
  15. 如請求項14所述之向量內積計算裝置，其中該向量資料前累加器產生之每一該累加結果為其對應之該邏輯”1”的總數目。
  16. 如請求項9所述之向量內積計算裝置，其中該數字轉換器與該後累加器整合為一進位保留加法器(carry-save adder)。
TW109129650A 2020-08-28 2020-08-28 向量內積計算裝置 TWI777231B (zh)

Priority Applications (2)

Application Number Priority Date Filing Date Title
TW109129650A TWI777231B (zh) 2020-08-28 2020-08-28 向量內積計算裝置
US17/076,548 US11500964B2 (en) 2020-08-28 2020-10-21 Device for computing the inner product of vectors

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
TW109129650A TWI777231B (zh) 2020-08-28 2020-08-28 向量內積計算裝置

Publications (2)

Publication Number Publication Date
TW202209136A TW202209136A (zh) 2022-03-01
TWI777231B true TWI777231B (zh) 2022-09-11

Family

ID=80356709

Family Applications (1)

Application Number Title Priority Date Filing Date
TW109129650A TWI777231B (zh) 2020-08-28 2020-08-28 向量內積計算裝置

Country Status (2)

Country Link
US (1) US11500964B2 (zh)
TW (1) TWI777231B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12205670B2 (en) 2022-04-05 2025-01-21 Taiwan Semiconductor Manufacturing Company, Ltd. Memory system and operating method of memory system

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7873812B1 (en) * 2004-04-05 2011-01-18 Tibet MIMAR Method and system for efficient matrix multiplication in a SIMD processor architecture
TWI361379B (en) * 2006-02-06 2012-04-01 Via Tech Inc Dual mode floating point multiply accumulate unit
US10140252B2 (en) * 2017-02-28 2018-11-27 Microsoft Technology Licensing, Llc Hardware node with matrix-vector multiply tiles for neural network processing
TW201939266A (zh) * 2018-03-02 2019-10-01 國立清華大學 快速向量乘累加電路

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10496855B2 (en) * 2016-01-21 2019-12-03 Hewlett Packard Enterprise Development Lp Analog sub-matrix computing from input matrixes
US10664271B2 (en) * 2016-01-30 2020-05-26 Hewlett Packard Enterprise Development Lp Dot product engine with negation indicator
WO2017139342A1 (en) * 2016-02-08 2017-08-17 Spero Devices, Inc. Analog co-processor
US10311126B2 (en) * 2016-08-12 2019-06-04 International Business Machines Corporation Memory device for matrix-vector multiplications
US11934798B2 (en) * 2020-03-31 2024-03-19 Micron Technology, Inc. Counter-based multiplication using processing in memory
US11537861B2 (en) * 2020-06-23 2022-12-27 Micron Technology, Inc. Methods of performing processing-in-memory operations, and related devices and systems

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7873812B1 (en) * 2004-04-05 2011-01-18 Tibet MIMAR Method and system for efficient matrix multiplication in a SIMD processor architecture
TWI361379B (en) * 2006-02-06 2012-04-01 Via Tech Inc Dual mode floating point multiply accumulate unit
US10140252B2 (en) * 2017-02-28 2018-11-27 Microsoft Technology Licensing, Llc Hardware node with matrix-vector multiply tiles for neural network processing
TW201939266A (zh) * 2018-03-02 2019-10-01 國立清華大學 快速向量乘累加電路

Also Published As

Publication number Publication date
US11500964B2 (en) 2022-11-15
TW202209136A (zh) 2022-03-01
US20220067120A1 (en) 2022-03-03

Similar Documents

Publication Publication Date Title
US12175253B2 (en) Calculating device
US6081821A (en) Pipelined, high-precision fast fourier transform processor
EP0161089B1 (en) Double precision multiplier
CN100583024C (zh) 一种用于浮点除法和平方根运算的预处理电路结构
TW202136990A (zh) 用於批次歸一化的計算單元
US12282844B2 (en) Artificial intelligence accelerators
CN112464296B (zh) 一种用于同态加密技术的大整数乘法器硬件电路
CN107967132B (zh) 一种用于神经网络处理器的加法器和乘法器
TWI777231B (zh) 向量內積計算裝置
CN115495152A (zh) 变长输入的存内计算电路
US11861327B2 (en) Processor for fine-grain sparse integer and floating-point operations
CA2329104C (en) Method and apparatus for calculating a reciprocal
CN110532510B (zh) 一种生成旋转因子和校正因子的生成器
CN114780057B (zh) 基于Saber密钥封装的多项式硬件乘法器及使用方法
KR102832857B1 (ko) 세분화된 희소 정수 및 부동 소수점 연산들을 위한 프로세서
CN117193715A (zh) 面向后量子加密Kyber方案的NTT多项式乘法器的硬件电路
CN109379191B (zh) 一种基于椭圆曲线基点的点乘运算电路和方法
US20040186972A1 (en) Associated Content Storage System
CN118092855A (zh) 支持浮点数尾数乘法的存算一体乘法器及乘法运算方法
TWI749552B (zh) 內積計算裝置
KR100954843B1 (ko) 센서 모트에서의 블록 인덱싱 기반의 타원 곡선 암호 연산 방법, 그 장치 및 이를 기록한 기록 매체
CN111610955A (zh) 一种数据饱和加打包处理部件、芯片及设备
US20240378018A1 (en) Adder circuits for floating-point operation
US20250077180A1 (en) Bit-parallel digital compute-in-memory macro and associated method
CN116522967A (zh) 乘法器与芯片

Legal Events

Date Code Title Description
GD4A Issue of patent certificate for granted invention patent