Source: http://www.google.com/patents/US5889947?ie=ISO-8859-1
Timestamp: 2015-04-19 04:13:37
Document Index: 667201188

Matched Legal Cases: ['ART2', 'ART3', 'ART4', 'ART3', 'ART4', 'ART2', 'ART20', 'ART30', 'ART20', 'ART30', 'ART20', 'ART21', 'ART31', 'ART21', 'ART31', 'ART21', 'ART22', 'ART22', 'ART23', 'ART33', 'ART23', 'ART33', 'ART23']

Patent US5889947 - Apparatus and method for executing instructions that select a storage ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA multiprocessor computer system comprises a plurality of processors, wherein each processor includes an execution unit, a program counter, a result buffer containing a plurality of entries, each entry being allocated to hold an output value of an instruction executed by the execution unit, and an operation...http://www.google.com/patents/US5889947?utm_source=gb-gplus-sharePatent US5889947 - Apparatus and method for executing instructions that select a storage location for output values in response to an operation countAdvanced Patent SearchPublication numberUS5889947 APublication typeGrantApplication numberUS 08/767,406Publication dateMar 30, 1999Filing dateDec 16, 1996Priority dateDec 16, 1996Fee statusPaidAlso published asCN1095133C, CN1185609APublication number08767406, 767406, US 5889947 A, US 5889947A, US-A-5889947, US5889947 A, US5889947AInventorsWilliam John StarkeOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (5), Referenced by (9), Classifications (20), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetApparatus and method for executing instructions that select a storage location for output values in response to an operation count
US 5889947 AAbstract
A multiprocessor computer system comprises a plurality of processors, wherein each processor includes an execution unit, a program counter, a result buffer containing a plurality of entries, each entry being allocated to hold an output value of an instruction executed by the execution unit, and an operation counter containing an operation count that is incremented at least when an instruction storing an output value to the result buffer is executed by the execution unit. A particular entry allocated in the result buffer for a given output value is selected as a function of the operation count at the time the instruction generating that given output value is executed. Each processor further includes a decoder that extracts a processor identifier from an instruction to be executed that identifies one of the plurality of processors, wherein one or more input values of the instruction are retrieved from the result buffer of the identified processor. Each decoder also extracts a displacement value from the instruction to be executed that provides a relative difference between the current operation count of the executing processor and an expected operation count of the identified processor when the desired input values are stored in the result buffer of the identified processor. The decoder generates an access key as a function of the displacement value and the current operation count of the processor executing the instruction and retrieves an input value from the result buffer of the identified processor at the entry indexed by the access key.
1. An apparatus comprising:an execution unit, wherein said execution unit executes an instruction to generate an output value; a result buffer containing a plurality of entries, wherein an entry among said plurality of entries can be allocated to hold an output value of an instruction executed by said execution unit; and an operation counter containing an operation count that is incremented at least when an instruction storing an output value to said result buffer is executed by said execution unit, said instruction being associated with a single operation count contained by said operation counter when said instruction is executed, wherein a particular entry in said result buffer is allocated for a given output value in response to said single operation count associated with the instruction generating said given output value. 2. The apparatus of claim 1, wherein each output value in said result buffer is stored in association with a usage count, wherein each usage count indicates a number of times an associated output value will be used as an input specified by other instructions executed in another one or more apparatus.
7. A multiprocessor computer system comprising:a plurality of processors, wherein each processor includes:an execution unit, wherein said execution unit executes an instruction utilizing one or more input values to generate an output value; a result buffer containing a plurality of entries, wherein an entry among said plurality of entries can be allocated to hold an output value of an instruction executed by the execution unit; an operation counter containing an operation count that is incremented at least when an instruction storing an output value to the result buffer is executed by the execution unit, wherein a particular entry allocated in said result buffer for a given output value in response to said operation count when an instruction generating said given output value is executed; and a decoder that extracts a processor identifier from an instruction to be executed by said execution unit that identifies one of said plurality of processors, wherein one or more input values of said instruction are retrieved from said result buffer of said identified processor. 8. The multiprocessor computer system of claim 7, wherein each decoder extracts a displacement value from said instruction to be executed by said execution unit that provides a relative difference between an operation count of a processor executing said instruction and an expected operation count of said identified processor that is associated with the entry of said one or more input values in said result buffer of said identified processor, wherein said decoder generates an access key in response to said displacement value and an operation count of said processor executing said instruction and retrieves an input value from said result buffer of said identified processor at an entry associated with said access key.
13. A method of processing data in a data processing system, said method comprising:executing an instruction that generates an output value to be stored in a result buffer; incrementing an operation count to obtain a single operation count associated with said instruction; and storing the output value in an entry of the result buffer, wherein the entry is indicated by the single operation count associated with the instruction. 14. The method of claim 13, and further comprising the step of generating a usage count that is stored in the result buffer in association with the output value, wherein the usage count indicates a number of times the associated output value will be used as an input specified by other instructions executed in at least one other processor.
17. The method of claim 16, and further comprising the step of:preventing said displacement value from exceeding a selected amount. 18. A method of storing a result in a multiprocessing system having a plurality of processors, the method comprising:executing an instruction within one of the plurality of processors that generates a result; incrementing an operation count associated with the one processor in response to execution of said instruction, wherein the result is uniquely identified by its association with the one processor and the incremented operation count; and storing the result within the multiprocessing system such that the result is accessed in storage by any processor of the plurality of processors by its unique identity defined by the one processor and the incremented operation count. 19. The method of claim 18, and further comprising the step of generating a usage count that is stored in association with the result, wherein the usage count indicates a number of times the associated result will be used as an input specified by other instructions executed in one or more processors of the plurality of processors.
The present invention provides a multiprocessor computer system comprising a plurality of processors, wherein each processor includes an execution unit, a program counter, a result buffer containing a plurality of entries, each entry being allocated to hold an output value of an instruction executed by the execution unit, and an operation counter containing an operation count that is incremented at least when an instruction storing an output value to the result buffer is executed by the execution unit. A particular entry allocated in the result buffer for a given output value is selected as a function of the operation count at the time the instruction generating that given output value is executed. Each processor further includes a decoder that extracts a processor identifier from an instruction to be executed that identifies one of the plurality of processors, wherein one or more input values of the instruction are retrieved from the result buffer of the identified processor. Each decoder also extracts a displacement value from the instruction to be executed that provides a relative difference between the current operation count of the executing processor and an expected operation count of the identified processor when the desired input values are stored in the result buffer of the identified processor. The decoder generates an access key as a function of the displacement value and the current operation count of the processor executing the instruction and retrieves an input value from the result buffer of the identified processor at the entry indexed by the access key. The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
Emerging semiconductor technologies have made it viable to package an increasing number of circuits on a single chip. By placing multiple logical entities on the same chip instead of on different chips, a processor architect is able to utilize greatly increased data bandwidth and decreased latency. By placing an entire complex processor on a single chip, processor manufacturers have advanced the state of the art significantly. As densities increase, it becomes possible to develop single chip processors with increasing complexity, at an increasing cost, while experiencing diminishing performance gains.
EXAMPLE INSTRUCTION SET ARCHITECTURE
In order to illustrate the present invention, an example of a computer instruction set architecture for operation in the present invention is now described. First, a hypothetical computer instruction set architecture (A), indicative of the prior art is described. Next, an example program fragment is coded for the hypothetical architecture (A) of the prior art, and the execution of that program fragment on a number of typical computer implementations is discussed. Next, the hypothetical architecture is extended (A') to operate in the multiprocessor system of the preferred embodiment of the present invention. Next, the example program fragment is shown re-coded for the extended computer instruction set architecture (A') of a preferred embodiment of the present invention, and the execution of that re-coded program fragment on one example of a multiprocessor computer system according to the present invention is discussed.
The following defines a program fragment written for the hypothetical computer instruction set architecture (A). A mixture of assembler mnemonics and pseudo-code are used to indicate both the behavior of the algorithm as well as its implementation in terms of machine instructions, and should be easily understood by those skilled in the art. The ID associated with a given instruction is used later to concisely refer to that particular instruction.
______________________________________Label   Opcode    Operands            ID______________________________________START   LOAD      R1 &lt;- - MEM (R2 + OFFSET1)                                 I1   LOAD      R3 &lt;- - MEM (R2 + OFFSET2)                                 I2   ADD       R4 &lt;- - R1, R3      I3   LOAD      R5 &lt;- - MEM (R2 + OFFSET3)                                 I4   SUB       R6 &lt;- - R5, DELTA1  I5   MULT      R7 &lt;- - R4, R6      I6   LOAD      R8 &lt;- - MEM (R2 + OFFSET4)                                 I7   CMP       C1 &lt;- - R7, R8      I8   BLE       C1 - -&gt; PART2       I9   ADD       R9 &lt;- - R7, DELTA2  I10LOOP    LOAD      R10 &lt;- - MEM (R7 + OFFSET5)                                 I11   ADD       R11 &lt;- - R10, R9    I12   SUB       R12 &lt;- - R10, DELTA3                                 I13   LOAD      R13 &lt;- - MEM (R7 + OFFSET6)                                 I14   ADD       R14 &lt;- - R13, R9    I15   SUB       R15 &lt;- - R13, DETLTA4                                 I16   MULT      R16 &lt;- - R11, R15   I17   MULT      R17 &lt;- - R12, R14   I18   CMP       C2 &lt;- - R14, R11    I19   BLE       C2 - -&gt; PART3       I20   STORE     R16 - -&gt; MEM (R7 + OFFSET5)                                 I21   ADD       R18 &lt;- - R17, R16   I22   STORE     R18 - -&gt; MEM (R7 + OFFSET6)                                 I23   B&gt; PART4 I24PART3   STORE     R17 - -&gt; MEM (R7 + OFFSET5)                                 I25   SUB       R18 &lt;- - R17, R16   I26   STORE     R18 - -&gt; MEM (R7 + OFFSET6)                                 I27PART4   ADD       R7 &lt;- - R7, DELTA5  I28   CMP       C3 &lt;- - R7, LIMIT   I29   BLE       C3 - -&gt; LOOP        I30PART2   STORE     R7 - -&gt; MEM (R2 + OFFSET1)                                 I31   EXIT______________________________________
Due to the complexities introduced into instruction execution timings due to factors such as cache misses, branch prediction, and speculative execution, the timings shown for the present example make the following simplifying assumptions: a) all loads, stores, and instruction fetches hit in the cache, and thus cause no stall cycles; b) control flow dependencies must be resolved before execution may proceed, thus eliminating the factors typically involved with branch prediction and speculative execution. The effects of all these factors are, however, discussed when the timings for (A) and (A') are compared. Note that unconditional branches (I24) are folded, incurring no penalty and imposing no dependency. Due to the fact that there are multiple possible execution paths for the program fragment, only one is shown here, in which the main loop (I11 through I30) iterates twice, following the taken path for (I20) during the first iteration, and following the not-taken path for (I20) during the second iteration.
INSTRUCTION SET ARCHITECTURE OF THE PRESENT INVENTION
The present invention may be embodied either as a new instruction set architecture, which provides broad function with a greatly simplified underlying machine organization, or as an extension to an existing instruction set architecture, which enables the multiple processors in an SMP configuration of said architecture to act in concert to solve a single threaded problem more quickly. In the present example, the latter is described by showing the incorporation of the mechanisms of the present invention into the hypothetical computer instruction set architecture (A), yielding (A'). Also, in order to more fully describe the additional programming requirements imposed by result buffer management method M1, the preferred embodiment incorporates method M1.
SAMPLE PROGRAM FRAGMENT RE-CODED FOR THE EXTENDED ISA (A') OF THE PRESENT INVENTION
Below, the sample program fragment is shown encoded for execution on a preferred embodiment of the multiprocessor of the present invention. Additional extensions are defined to the standard set of pseudo-coded assembler mnemonics used in the earlier example. These extensions provide the programmer with a means to represent extensions available in (A') mnemonically.
______________________________________Action                 Mnemonic______________________________________Write a data value to the result buffer                  DRB(c) &lt;- . . .with a usage count of c.Write a condition code to the result                  CRB(c) &lt;- . . .buffer with a usage count of c.Read a data value from the result buffer                  . . . &lt;-- DRBp(d)of processor p with an operation count                  DRBp(d) --&gt; . . .displacement of d (-4, -3, -2, -1)Read a condition code from the result                  CRBp(-1) --&gt; . . .buffer of processor p with an operationcount displacement of -1.______________________________________
PROCESSOR 0 CODE FRAGMENT
Initial state: CPUO's DRB(O) contains base address with ref count of 3 CPUO's Register R2 also contains same base address
______________________________________Label  Opcode    Operands            ID______________________________________  SPAWN     CPU1 --&gt; STRM1      IA  SPAWN     CPU2 --&gt; STRM2      IBSTRM0  LOAD      R1 &lt;-- MEM(R2 + OFFSET1)                                I1  ADD       DRB(1) &lt;- R1, DRB1(-1)                                I3  NOOP                          IC  COPY      R7 &lt;-- DRB2(-1)     ID  BLE       CRB3(-1) --&gt; PART20 I9  ADD       R9 &lt;-- R7, DELTA2   I10LOOP0  NOOP                          IE  ADD       DRB(2) &lt;- DRB1(-1), R9                                I12  MULT      DRB(2) &lt;- DRB0(-1), DRB2(-1)                                I17  BLE       CRB3(-1) --&gt; PART30 I20  STORE     DRB0(-2)-&gt; MEM(R7 + OFFSET5)                                I21  ADD       R7 &lt;-- R7, DELTA5   I28a  BLE       CRB2(-1) --&gt; LOOP0  I30a  B&gt; PART20  IFPART30 STORE     DRB1(-2)-&gt; MEM(R7 + OFFSET5)                                I25  ADD       R7 &lt;-- R7, DELTA5   I28b  BLE       CRB2(-1) --&gt; LOOP0  I30bPART20 STORE     R7 --&gt; MEM (R2 + OFFSET1)                                I31  EXIT______________________________________
PROCESSOR 1 CODE FRAGMENT
______________________________________Label  Opcode   Operands              ID______________________________________  SPAWN    CPU3 --&gt; STRM3        IGSTRM1  LOAD     DRB(1) &lt;- MEM(DRB0(-3) + OFFSET2)                                 I2  NOOP                           IH  NOOP                           II  COPY     R7 &lt;-- DRB2(-1)       IJ  BLE      CRB3(-1) --&gt; PART21   I9  NOOP                           IKLOOP1  LOAD     DRB(2) &lt;- MEM (R7 + OFFSET5)                                 I11  SUB      R12 &lt;-- DRB1(-1), DELTA3                                 I13  MULT     DRB(2) &lt;- R12, DRB3(-1)                                 I18  BLE      CRR3(-1) --&gt; PART31   I20  NOOP     &lt;-- DRB1(-2)          IL  ADD      R7 &lt;-- R7, DELTA5     I28a  BLE      CRB2(-1) --&gt; LOOP1    I30a  B&gt; PART21  IMPART31 NOOP     &lt;-- DRB0(-2)          IN  ADD      R7 &lt;-- R7, DELTA5     I28b  BLE      CRB2(-1) --&gt; LOOP1    I30bPART21 NOOP                           I0  EXIT______________________________________
PROCESSOR 2 CODE FRAGMENT
______________________________________Label  Opcode   Operands              ID______________________________________STRM2  LOAD     R5 &lt;-- MEM(DRB0(-3) + OFFSET3)                                 I4  SUB      R6 &lt;-- R5, DELTA1     I5  MULT     DRB(5) &lt;- DRB0(-1), R6                                 I6  COPY     R7 &lt;-- DRB2(-1)       IP  BLE      CRB3(-1) --&gt; PART22   I9  NOOP                           IQLOOP2  LOAD     DRB(2) &lt;- MEM (R7 + OFFSET6)                                 I14  SUB      DRB(1) &lt;- DRB2(-1), DELTA4                                 I16  COPY     DRB(1) &lt;- R7          IR  NOOP                           IS  ADD      R7 &lt;-- R7, DELTA5     I28  CMP      CRB(4) &lt;- R7, LIMIT   I29  BLE      CRB2(-1) --&gt; LOOP2    I30  NOOP                           ITPART22 NOOP                           IU  EXIT______________________________________
PROCESSOR 3 CODE FRAGMENT
______________________________________Label  Opcode   Operands             ID______________________________________STRM3  LOAD     R8 &lt;-- MEM(DRB0(-3) + OFFSET4)                                I7  NOOP                          IV  NOOP                          IW  CMP      CRB(4) &lt;- DRB2(-1), R8                                I8  BLE      CRB3(-1) --&gt; PART23  I9  ADD      R9 &lt;-- DRB2(-3), DELTA2                                I10LOOP3  NOOP                          IX  ADD      DRB(2) &lt;- DRB2(-1), R9                                I15  CMP      CRB(3) &lt;- DRB3(-1), DRB0(-1)                                I19  BLE      CRB3(-1) --&gt; PART33  I20  ADD      R15 &lt;-- DRB0(-2), DRB1(-2)                                I22  STORE    R15 -&gt; MEM(DRB2(-3) + OFFSET6)                                I23  BLE      CRB2(-1) --&gt; LOOP3   I30a  B&gt; PART23  IYPART33 SUB      R15 &lt;-- DRB0(-2), DRB1(-2)                                I26  STORE    R15 -&gt; MEM(DRB2(-3) + OFFSET6)                                I27  BLE      CRB2(-1) --&gt; LOOP3   I30bPART23 NOOP                          IZ  EXIT______________________________________
The following shows the cycle-by-cycle execution behavior of the four co-requisite program fragments when executed simultaneously on four "simple" processors of an SMP extended as prescribed by the present embodiment. Note that the timings shown assume the same simplifications as did the previous timing examples, and show the code following the same execution path as it did in the previous timing examples.
EXECUTION TIMING FOR THE SAMPLE COREQUISITE PROGRAM FRAGMENTS ON THE EXTENDED ISA OF THE PRESENT INVENTION
______________________________________Cycle    CPU0      CPU1      CPU2    CPU3______________________________________ 1       IA        ?         ?       ? 2       IB        IG        ?       ? 3       I1        I2        I4      I7 4       I3        IH        I5      IV 5       IC        II        I6      IW 6       ID        IJ        IP      I8 7       I9 (N)    I9 (N)    I9(N)   I9 (N) 8       I10       IK        IQ      I10 9       IE        I11       I14     IX10       I12       I13       I16     I1511       I17       I18       IR      I1912       I20 (T)   I20(T)    IS      I20 (T)13       I25       IN        I28     I2614       I28b      I28b      I29     I2715       I30b(T)   I30b(T)   I30(T)  I30b(T)16       IE        I11       I14     IX17       I12       I13       I16     I1518       I17       I18       IR      I1919       I20(N)    I20(N)    IS      I20 (N)20       I21       IL        I28     I2221       I28a      I28a      I29     I2322       I30a(N)   I30a(N)   I30(N)  I30a(N)23       IF        IM        IT      IY24       I31       IO        IU      IZ______________________________________
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4617625 *Dec 27, 1982Oct 14, 1986Hitachi, Ltd.Vector processorUS5237694 *May 30, 1991Aug 17, 1993Advanced Micro Devices, Inc.Processing system and method including lock buffer for controlling exclusive critical problem accesses by each processorUS5297255 *Jan 27, 1989Mar 22, 1994Hitachi, Ltd.Parallel computer comprised of processor elements having a local memory and an enhanced data transfer mechanismUS5347639 *Jul 15, 1991Sep 13, 1994International Business Machines CorporationSelf-parallelizing computer system and methodUS5535346 *Jul 5, 1994Jul 9, 1996Motorola, Inc.Data processor with future file with parallel update and method of operation* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6188948Oct 1, 1999Feb 13, 2001Navistar International Transportation Corp.Vehicle anti-lock brake systems assembly verification systemUS6643763Feb 28, 2000Nov 4, 2003International Business Machines CorporationRegister pipe for multi-processing engine environmentUS6763449 *Oct 23, 2000Jul 13, 2004Fujitsu LimitedOperation-processing apparatusUS6915367 *Oct 30, 2003Jul 5, 2005Stmicroelectronics, Inc.Shared peripheral architectureUS7624295 *Oct 25, 2004Nov 24, 2009Panasonic CorporationProcessor system, instruction sequence optimization device, and instruction sequence optimization programUS7805540 *Dec 20, 2005Sep 28, 2010Cisco Technology, Inc.Method and system for reprogramming instructions for a switchUS8381037 *Oct 9, 2003Feb 19, 2013International Business Machines CorporationMethod and system for autonomic execution path selection in an applicationUS8606960 *Dec 9, 2002Dec 10, 2013Intel CorporationMethod and apparatus for improving packet processingUS20040111522 *Dec 9, 2002Jun 10, 2004Johnson Erik J.Method and apparatus for improving packet processing* Cited by examinerClassifications U.S. Classification709/213, 700/5, 709/216, 712/E09.053, 711/164, 713/502, 712/E09.032, 712/E09.035International ClassificationG06F9/318, G06F9/30, G06F9/38, G06F9/52Cooperative ClassificationG06F9/30185, G06F9/30087, G06F9/3826, G06F9/3851, G06F9/3838European ClassificationG06F9/30X, G06F9/30A8S, G06F9/38E4Legal EventsDateCodeEventDescriptionJul 16, 2010FPAYFee paymentYear of fee payment: 12Jun 30, 2006FPAYFee paymentYear of fee payment: 8Jul 16, 2002FPAYFee paymentYear of fee payment: 4Nov 2, 1999CCCertificate of correctionDec 16, 1996ASAssignmentOwner name: INTERNATIONAL BUSINESS MACHINES CORPORATION, NEW YFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:STARKE, WILLIAM J.;REEL/FRAME:008374/0744Effective date: 19961211RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services