Source: http://www.google.com/patents/US8024551?dq=6437692
Timestamp: 2014-10-23 02:21:46
Document Index: 157055681

Matched Legal Cases: ['art 114', 'Application No. 200680039988', 'Application No. 200680039988', 'Application No. 200680039988', 'Application No. 200680047898', 'Application No. 2008537761', 'Application No. 095139557', 'Application No. 095139563', 'Application No. 06817002', 'Application No. 06817042', 'Application No. 06817042', 'Application No. 06817002', 'Application No. 06817042']

Patent US8024551 - Pipelined digital signal processor - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsReducing pipeline stall between a compute unit and address unit in a processor can be accomplished by computing results in a compute unit in response to instructions of an algorithm; storing in a local random access memory array in a compute unit predetermined sets of functions, related to the computed...http://www.google.com/patents/US8024551?utm_source=gb-gplus-sharePatent US8024551 - Pipelined digital signal processorAdvanced Patent SearchPublication numberUS8024551 B2Publication typeGrantApplication numberUS 11/258,801Publication dateSep 20, 2011Filing dateOct 26, 2005Priority dateOct 26, 2005Also published asCN101297279A, CN101297279B, EP1941378A2, EP1941378A4, US8458445, US20070094483, US20110296145, WO2007050361A2, WO2007050361A3Publication number11258801, 258801, US 8024551 B2, US 8024551B2, US-B2-8024551, US8024551 B2, US8024551B2InventorsJames Wilson, Joshua A. Kablotsky, Yosef Stein, Colm J. Prendergast, Gregory M. Yukna, Christopher M. MayerOriginal AssigneeAnalog Devices, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (73), Non-Patent Citations (32), Referenced by (1), Classifications (8), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetPipelined digital signal processorUS 8024551 B2Abstract Reducing pipeline stall between a compute unit and address unit in a processor can be accomplished by computing results in a compute unit in response to instructions of an algorithm; storing in a local random access memory array in a compute unit predetermined sets of functions, related to the computed results for predetermined sets of instructions of the algorithm; and providing within the compute unit direct mapping of computed results to related function.
FIELD OF THE INVENTION This invention relates to a pipelined digital signal processor for avoiding pipeline stall between compute unit and address unit.
BACKGROUND OF THE INVENTION As computer speed increased from 33 mHz to 1.2 GHz and beyond, the computer operations could not be completed in one cycle. As a result the technique of pipelining was adopted to make most efficient use of the higher processor performance and to improve their throughput. Presently deep pipelining uses as many as 25 stages or more. Generally, in a pipelined computing system there are several parallel building blocks working simultaneously where each block takes care of different parts of the whole process for example, there is a compute unit that does the computation, an address unit including a data address generator (DAG) that fetches and stores the data in memory according to the selected address modes and a sequencer or control circuit that decodes and distributes the instructions. The DAG is the only component that can address the memory. Thus in a deeply pipelined system if an instruction is dependent on the result of another one, a pipeline stall will happen where the pipeline will stop, waiting for the offending instruction to finish before resuming work. For example, if, after a computation, the output of the computing unit is needed by the DAG for the next data fetch, it can't be delivered directly to the DAG to be conditioned for a data fetch: it must propagate through the pipeline before it can be processed by the DAG to do the next data fetch and computation. This is so because only the DAG has access to the memory and can convert the compute result to an address pointer to locate the desired data. In multi-tasking general purpose computers this stall may not be critical but in real time computer systems such as used in e.g., cell phones, digital cameras, these stalls are a problem.
SUMMARY OF THE INVENTION It is therefore an object of this invention to provide an improved pipelined digital signal processor for minimizing pipeline stall between compute unit and address unit.
Suppose a compute unit computes a result which is an angle α, but it is a function of that angle, sine α, that is to be used in the execution of the subsequent operation. Then the compute unit must deliver the computed result to address unit 12 where DAG 14 or 16 generates the proper address to fetch from memory 30 or 36 the assigned function of that angle and bring it back and submit it to the compute unit. This stall or break in the pipeline wastes time. One feature of DSP 10 is that address unit 12 and only address unit 12 can address memories 30 and 36. Thus any time a compute unit needs information from L1 memory 30 or L3 memory 36 to operate, the pipelining operations become stalled due to the fact that the compute unit result is valid at a stage later than when the DAG 12 register is loaded This can be better understood with respect to the chart in FIG. 2 where it can be seen, for example, that the instruction fetch takes four machine cycles, IF1, IF2, IF3, IF4. The digital address generation requires two machines cycles DAG1, DAG2 and the data fetch four more machine cycles, DF1, DF2, DF3, DF4. The compute operation requires three cycles CF1, CF2, CF3 to obtain the computed result C1. Thus if a compute unit result from stage C1 is needed by the DAG of the next instruction it must �swim up� the pipeline and wait for stage D to be executed before the DAG register is loaded. This is a graphic example of pipeline stall.
Alternatively, in communication type of applications, FIG. 7, the same computed result b0 α may be placed in each portion 106, 108, 110, 112 of input register 100 c so that they identify four parts of one value. For example, four parts of the sine of α. Each part being in a part 114, 116, 118, 120 of output register 102 c and being 8 bits so that when combined they produced a 32 bit accuracy value for this sine α. Each local reconfigurable fill and spill random access memory array 50 a, 50 b, 50 c, 50 d may contain 256 8 bit values and may have their data structure arranged in a number of different ways. For example, FIG. 8A, local reconfigurable fill and spill random access memory array 50 a may provide 8, 8 bit values 130 or each may provide different s-box values for an DES encryption as at 132, 134, 136, 138. The data may be structured across all of the local reconfigurable fill and spill random access memory arrays as at 140 providing 32 bit values such as for VLD decoding. Or just two of the local reconfigurable fill and spill random access memory arrays 50 a, 50 b may be employed 142 to access the sine value at 16 bit accuracy. As can be seen the data structure is quite facile. Further it need not be limited to the side by side arrangement shown in FIG. 8A: it may be in a two over two arrangement as shown in FIG. 8B to provide 512 positions with up to 16 bits across. Although in FIG. 8A the sets of S-box values 132, 134, 136, 138 are stored in the same locations �63� across each memory array, LUT's 50 a-d, this is not a necessary limitation of the invention. By adding a table base register 51 a-d with each array, LUT's 50 a-d they may be stored at any different, available locations in each array. For example, S-box 2, 3 and 4, a 64 entries LUT 134, 136, 138 could be stored starting at location �0� or S-box 2 could be stored starting at location �0� while S-box 3 and 4, 136, 138 could be stored starting at location �191�. In this way related sets of data, e.g. S-box 1-4, 1/GF(x1-4) need not be stored at the same location across all memory arrays 50 a-d but can be stored at independent addresses in each array.
The fact that a local reconfigurable fill and spill random access memory array with as few as 256 8 bit values can make a huge impact on the avoidance of pipeline stall is illustrated with respect to a variable length decoding (VLD) application as explained with reference to FIGS. 9-12. In such an application the variable length code takes advantage of the fact that certain code values are going to occur more often then others. If frequently occurring values are assigned short length code words and infrequently ones transmitted using longer code words an effective bite rate reduction will be obtained. As an analogy, if English text was being transmitted �a�, �e�, �i� would be sent with short code words whereas �z� would be sent using a long code word. For example, a, b, c, d, e, f . . . are coded with variable length keys as shown by the graphic depiction in FIG. 9. The symbol a is represented by 0, the symbol b by 01, the symbol c by 100, the symbol d by 101, the symbol e by 110, the symbol f by 1110, symbol g by 11110 and so on. Thus upon receipt of a VLD input bit stream, FIG. 10, by bit-FIFO register 140, an inspection of n bits where n equals to 8 is made as at 150, FIG. 11. The inspected 8-bit field is used as an address into the compute unit 256 entries VLD LUT. The LUT entry can be marked as an identified symbol 152 (MSB is set to �1�) or it can mark that more bits are needed to identified the symbol 166 (MSB is set to �0�). In the case where a symbol is identified the LUT entry holds the value 156 of the decoded symbol as well is how many bits 154 to remove (extract) from the bit stream to start the inspection of the next symbol. In the case 166 where more bits are needed the LUT entry holds an indication of how many additional bit stream bits are needed to complete the identification 168 as well as a pointer 176 to another L1-LUT that is responsible for the identification of all the symbols that are longer than 8 bits. This process is terminated when an LUT entry is marked as symbol identified 170. Note that in the first two examples in FIG. 11, the local reconfigurable fill and spill random access memory array satisfied all the requirements internally, no external memory was needed and so pipeline stall was avoided. However, in the third example the local reconfigurable fill and spill random access memory array could not satisfy the need and an external memory had to be consulted causing pipeline stall.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3303477Oct 8, 1964Feb 7, 1967Telefunken PatentApparatus for forming effective memory addressesUS3805037Feb 22, 1972Apr 16, 1974Ellison JN{40 th power galois linear gateUS3959638Feb 6, 1975May 25, 1976International Business Machines CorporationHighly available computer systemUS4757506Jan 9, 1987Jul 12, 1988Ant Nachrichtentechnik GmbhMethod of decoding binary signals and viterbi decoder as well as uses thereforUS5031131 *Oct 1, 1990Jul 9, 1991Eaton CorporationDirect digital synthesizerUS5062057Dec 9, 1988Oct 29, 1991E-Machines IncorporatedComputer display controller with reconfigurable frame buffer memoryUS5101338Apr 27, 1989Mar 31, 1992Nec CorporationMemory access control device which can be formed by a reduced number of lsi'sUS5260898 *Mar 13, 1992Nov 9, 1993Sun Microsystems, Inc.Result cache for complex arithmetic unitsUS5287511Oct 15, 1991Feb 15, 1994Star Semiconductor CorporationArchitectures and methods for dividing processing tasks into tasks for a programmable real time signal processor and tasks for a decision making microprocessor interfacing therewithUS5351047Sep 21, 1992Sep 27, 1994Laboratory Automation, Inc.Data decoding method and apparatusUS5386523Jan 10, 1992Jan 31, 1995Digital Equipment CorporationAddressing scheme for accessing a portion of a large memory spaceUS5530825 *Apr 15, 1994Jun 25, 1996Motorola, Inc.Data processor with branch target address cache and method of operationUS5537579 *Feb 18, 1994Jul 16, 1996Fujitsu LimitedMethod and apparatus for managing color dataUS5666116Dec 1, 1995Sep 9, 1997U.S. Philips CorporationHigh speed variable-length decoder arrangementUS5675332Feb 1, 1996Oct 7, 1997Samsung Electronics Co., Ltd.Plural-step chunk-at-a-time decoder for variable-length codes of Huffman typeUS5689452Oct 31, 1994Nov 18, 1997University Of New MexicoMethod and apparatus for performing arithmetic in large galois field GF(2n)US5696941Feb 1, 1995Dec 9, 1997Samsung Electronics Co., Ltd.Device for converting data using look-up tablesUS5710939May 26, 1995Jan 20, 1998National Semiconductor CorporationBidirectional parallel data port having multiple data transfer rates, master, and slave operation modes, and selective data transfer terminationUS5819102Mar 25, 1996Oct 6, 1998Lotus CorporationFormula processor having cache means for storing and retrieving results of previously computed formulas base on identification and dependency informationsUS5832290Jan 17, 1997Nov 3, 1998Hewlett-Packard Co.Apparatus, systems and method for improving memory bandwidth utilization in vector processing systemsUS5961640Apr 22, 1997Oct 5, 1999Vlsi Technology, Inc.Virtual contiguous FIFO having the provision of packet-driven automatic endian conversionUS5970241Nov 19, 1997Oct 19, 1999Texas Instruments IncorporatedMaintaining synchronism between a processor pipeline and subsystem pipelines during debugging of a data processing systemUS5996057Apr 17, 1998Nov 30, 1999AppleData processing system and method of permutation with replication within a vector register fileUS5996066 *Oct 10, 1996Nov 30, 1999Sun Microsystems, Inc.Partitioned multiply and add/subtract instruction for CPU with integrated graphics functionsUS6009499Mar 31, 1997Dec 28, 1999Sun Microsystems, IncPipelined stack caching circuitUS6029242Oct 20, 1997Feb 22, 2000Sharp Electronics CorporationData processing system using a shared register bank and a plurality of processorsUS6061749Feb 18, 1998May 9, 2000Canon Kabushiki KaishaTransformation of a first dataword received from a FIFO into an input register and subsequent dataword from the FIFO into a normalized output datawordUS6067609Apr 9, 1998May 23, 2000Teranex, Inc.Pattern generation and shift plane operations for a mesh connected computerUS6094726Feb 5, 1998Jul 25, 2000George S. ShengDigital signal processor using a reconfigurable array of macrocellsUS6134676Apr 30, 1998Oct 17, 2000International Business Machines CorporationProgrammable hardware event monitoring methodUS6138208Apr 13, 1998Oct 24, 2000International Business Machines CorporationMultiple level cache memory with overlapped L1 and L2 memory accessUS6151705Oct 30, 1997Nov 21, 2000Hewlett-Packard CompanyEfficient use of the base register auto-increment feature of memory access instructionsUS6223320Feb 10, 1998Apr 24, 2001International Business Machines CorporationEfficient CRC generation utilizing parallel table lookup operationsUS6230179Dec 24, 1997May 8, 2001Motorola, Inc.Finite field multiplier with intrinsic modular reductionUS6263420Jul 14, 1998Jul 17, 2001Sony CorporationDigital signal processor particularly suited for decoding digital audioUS6272452Apr 2, 1998Aug 7, 2001Ati Technologies, Inc.Universal asynchronous receiver transmitter (UART) emulation stage for modem communicationUS6285607Mar 23, 1999Sep 4, 2001Memory Corporation PlcMemory systemUS6332188Nov 6, 1998Dec 18, 2001Analog Devices, Inc.Digital signal processor with bit FIFOUS6430672Jul 17, 2000Aug 6, 2002International Business Machines CorporationMethod for performing address mapping using two lookup tablesUS6480845Jun 14, 2000Nov 12, 2002Bull Hn Information Systems Inc.Method and data processing system for emulating virtual memory working spacesUS6539477Mar 3, 2000Mar 25, 2003Chameleon Systems, Inc.System and method for control synthesis using a reachable states look-up tableUS6587864Jan 18, 2002Jul 1, 2003Analog Devices, Inc.Galois field linear transformerUS6757806Dec 27, 2001Jun 29, 2004Hynix Semiconductor Inc.Method for converting addresses in a semiconductor memory device and apparatus thereforUS6771196Nov 12, 2002Aug 3, 2004Broadcom CorporationProgrammable variable-length decoderUS6829694Apr 24, 2002Dec 7, 2004Analog Devices, Inc.Reconfigurable parallel look up table systemUS7173985Aug 5, 2002Feb 6, 2007Altera CorporationMethod and apparatus for implementing a Viterbi decoderUS7187729Jan 10, 2003Mar 6, 2007Matsushita Electric Industrial Co., Ltd.Viterbi decoderUS7243210May 31, 2005Jul 10, 2007Atmel CorporationExtracted-index addressing of byte-addressable memoriesUS7424597Mar 31, 2003Sep 9, 2008Hewlett-Packard Development Company, L.P.Variable reordering (Mux) instructions for parallel table lookups from registersUS7728744Sep 13, 2007Jun 1, 2010Analog Devices, Inc.Variable length decoder system and methodUS7882284Mar 26, 2007Feb 1, 2011Analog Devices, Inc.Compute unit with an internal bit FIFO circuitUS20030085822Jul 25, 2001May 8, 2003Scheuermann W. JamesHigh performance memory efficient variable-length coding decoderUS20030103626Jun 12, 2002Jun 5, 2003Yosef SteinProgrammable data encryption engineUS20030133568Sep 26, 2002Jul 17, 2003Yosef SteinProgrammable data encryption engine for advanced encryption standard algorithmUS20030149857 *Apr 24, 2002Aug 7, 2003Yosef SteinReconfigurable parallel look up table systemUS20030196072Apr 11, 2002Oct 16, 2003Chinnakonda Murali S.Digital signal processor architecture for high computation speedUS20030229769Jun 7, 2002Dec 11, 2003Montemayor Oscar A.Using short references to access program elements in a large address spaceUS20040145942May 15, 2002Jul 29, 2004Katarzyna Leijten-NowakReconfigurable logic deviceUS20040193850Mar 31, 2003Sep 30, 2004Lee Ruby BVariable reordering (Mux) instructions for parallel table lookups from registersUS20040210618Jan 7, 2004Oct 21, 2004Yosef SteinGalois field linear transformer trellis systemUS20050086452Dec 7, 2004Apr 21, 2005Ross Jay B.Enhanced boolean processor with parallel inputUS20050228966 *Mar 16, 2004Oct 13, 2005Kabushiki Kaisha ToshibaProcessor system and data processing methodUS20050267996Mar 30, 2005Dec 1, 2005O'connor James MMethod frame storage using multiple memory circuitsUS20060143554Dec 23, 2004Jun 29, 2006Raghavan SudhakarScalable traceback technique for channel decoderUS20060271763May 31, 2005Nov 30, 2006Ronny PedersenExtracted-index addressing of byte-addressable memoriesUS20070044008Sep 27, 2006Feb 22, 2007Mediatek, Inc.ACS circuit and Viterbi decoder with the circuitUS20070089043Sep 28, 2006Apr 19, 2007Samsung Electronics Co., Ltd.Viterbi decoder and Viterbi decoding methodUS20070094474Oct 26, 2005Apr 26, 2007James WilsonLookup table addressing system and methodUS20080010439Sep 13, 2007Jan 10, 2008Yosef SteinVariable length decoder system and methodUS20080244237Mar 26, 2007Oct 2, 2008James WilsonCompute unit with an internal bit FIFO circuitUS20090089649Sep 27, 2007Apr 2, 2009James WilsonProgrammable compute unit with internal register and bit FIFO for executing Viterbi codeJP2001210357A Title not availableWO2003067364A2Nov 27, 2002Aug 14, 2003Analog Devices IncReconfigurable parallel look up table system* Cited by examinerNon-Patent CitationsReference1 *"Microsoft computer dictionary", 2002, Microsoft press, 5th edition, p. 474.2Citron, D. e t al., "Accelerating Multi-Media Processing by Implementing Memoing in Multiplication and Division Units", ACM Sigplan Notices, ACM, Association for Computing Machinery, NY, NY, vol. 33, No. 11, Nov. 1998, pp. 252-261.3English translation of Office Action for Chinese Patent Application No. 200680039988.6, mailed Dec. 4, 2009, 4 pages.4English translation of Office Action for Chinese Patent Application No. 200680039988.6, mailed Jun. 10, 2010, 6 pages.5English translation of Office Action for Chinese Patent Application No. 200680039988.6, mailed Jun. 19, 2009, 7 pages.6English translation of Office Action for Chinese Patent Application No. 200680047898.1, mailed Jan. 8, 2010, 5 pages.7English translation of Office Action for Japanese Patent Application No. 2008537761, mailed Mar. 8, 2011, 5 pages.8English translation of Office Action for Taiwan Patent Application No. 095139557, mailed Sep. 29, 2009, 5 pages.9English translation of Office Action for Taiwan Patent Application No. 095139563, mailed Jul. 14, 2010, 7 pages.10Examination Report for European Patent Application No. 06817002.6 mailed Sep. 16, 2009, 5 pages.11Examination Report for European Patent Application No. 06817042.2 mailed May 26, 2010, 6 pages.12Examination Report for European Patent Application No. 06817042.2, mailed May 26, 2010, 6 pages.13 *Gregory Goslin, "A guide to using field programmable gate arrays for application specific digital signal processing performance", 1995, Xilinx.14Hendrix et al., "Viterbi Decoding Techniques for the TMS32054x DSP Generation," Texas Instruments, Application Report SPRA071A-Jan. 2002, pp. 1-8.15 *Hennessy, John L., Patterson, David A. "Computer Organization and Design: The Hardware/Software Interface" Morgan Kaufmann Publishers, 2nd edition, 1998, pp. 449-465.16INTEL, Pentium Processor Family Developers Manual, [online], vol. 3, Architecture and Programming Manual, 1995, [retrieved Dec. 7, 2009]. Retrieved from the Internet: , retrieved Dec. 7, 2009, 1032 pages.17INTEL, Pentium Processor Family Developers Manual, [online], vol. 3, Architecture and Programming Manual, 1995, [retrieved Dec. 7, 2009]. Retrieved from the Internet: <http://download.intel.com/design/pentium/MANUALS/24143004.pdf>, retrieved Dec. 7, 2009, 1032 pages.18International Search Report for International Application No. PCT/US2006/040414, mailed Oct. 1, 2007, 1 page.19International Search Report for International Application No. PCT/US2006/040510, mailed Oct. 17, 2007, 2 pages.20International Search Report for International Application No. PCT/US2008/002914, mailed Jun. 27, 2008, 1 page.21International Search Report for International Application No. PCT/US2008/010524, mailed Nov. 28, 2008, 1 page.22International Search Report for International Application No. PCT/US2008/010571, mailed Nov. 25, 2008, 2 pages.23Rasheed et al., "Reconfigurable Viterbi Decoder for Mobile Platform," Mobile Communications Department, Institut Eurecom Sophia Antipolis, France, 3 pages.24Richardson, S.E., "Exploiting Trivial and Redundant Computation", Computer Arithmetic, 1993, Proceedings, 11th Symposium on Windsor, Ont., Canada, Jun. 29-Jul. 2, 1993, Los Alamitos, CA, USA, IEEE Comput. Soc., Jun. 1993 pp. 220-227.25Supplementary European Search Report and Opinion for European Patent Application No. 06817002.6, mailed Mar. 17, 2009, 5 pages.26Supplementary European Search Report and Opinion for European Patent Application No. 06817042.2, mailed Nov. 17, 2008, 8 pages.27Written Opinion for International Application No. PCT/US2006/040414, mailed Oct. 1, 2007, 7 pages.28Written Opinion for International Application No. PCT/US2006/040510, mailed Oct. 17, 2007, 9 pages.29Written Opinion for International Application No. PCT/US2008/002914, mailed Jun. 27, 2008, 4 pages.30Written Opinion for International Application No. PCT/US2008/010524, mailed Nov. 28, 2008, 7 pages.31Written Opinion for International Application No. PCT/US2008/010571, mailed Nov. 25, 2008, 4 pages.32Yadav et al., "Software-Only Multiple Variable Length Decoding for Real-Time Video on MDSP," International Conference on Consumer Electronics, 2005, ICCE, 2005 Digest of Technical Papers, Jan. 8-12, 2005, DOI: 0-7803-8838-0/05 2005, pp. 141-142.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8099655 *Dec 20, 2007Jan 17, 2012Pmc-Sierra Us, Inc.Galois field multiplier system and method* Cited by examinerClassifications U.S. Classification712/220International ClassificationG06F9/00Cooperative ClassificationG06F9/3885, G06F9/3001, G06F9/345European ClassificationG06F9/345, G06F9/38T, G06F9/30A1ALegal EventsDateCodeEventDescriptionNov 1, 2011CCCertificate of correctionOct 26, 2005ASAssignmentOwner name: ANALOG DEVICES, INC., MASSACHUSETTSFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:WILSON, JAMES;KABLOTSKY, JOSHUA A.;STEIN, YOSEF;AND OTHERS;REEL/FRAME:017152/0935Effective date: 20051010RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google