Spawn-join instruction set architecture for providing...

Details Spawn-join instruction set architecture for providing... Spawn-join instruction set architecture for providing...

1999-09-07

2002-10-08

Pan, Daniel H. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Processing sequence control

C712S228000, C712S219000, C712S242000, C709S241000, C709S241000, C709S241000

Reexamination Certificate

active

06463527

ABSTRACT:

BACKGROUND OF INVENTION
The way commodity computers have been designed is based on the so-called “von-Neumann architecture,” which dates back to 1946. The computer program, in the form of instruction-code, is stored in the computer memory. Each instruction of the program is then executed sequentially by the computer. A single program-counter (PC) is used to track the next instruction to be used. This next instruction is either the successor of the present instruction in the stored program, or some other instruction as designated by a jump or branch command.
Consider the following standard code which is provided as an example to demonstrate this current practice.
For i=1 to n do
Begin
A(i)=B(i)+i
End
C=D
FIG. 1
shows the steps followed when the above standard code is executed by a processing element using a standard program counter. Each step 10 in the For i=1 to n loop is executed serially. When the loop is completed, the next command
12
is executed. Current instruction code ends each loop with a branch command, which in all but the last iteration will direct the execution to another iteration of the loop. The branch command is used for the sole purpose of sequencing instructions for execution and results in a serial order of execution, where only one instruction is scheduled for execution at a time. The generic one-processor “Random Access Machine (RAM)” model of computation assumes that instructions are executed sequentially, one after another, with no concurrent operations and where each primitive operation takes a unit of time. As the number of transistors on an integrated circuit or chip doubles every 1-2 years, the challenge of making effective use of the computational power of a chip needs to be addressed in new ways.
All major computer vendors have announced processors exhibiting ILP in the last few years. Examples include: Intel P6, AMD K5, Sun UltraSPARC, DEC Alpha 21164, MIPS R10000, PowerPC 640/620 and HP 8000. These processors tend to deviate from the typical RAM sequential abstraction in two main ways to employ ILP: (i) Pipelining—each instruction executes in stages, where different instructions may be at different stages at the same time; and (ii) Multiple-issue—several instructions can be issued at the same time unit. The parallelism resulting from such overlap in time in the execution of different instructions is what is called “instruction-level parallelism (ILP).”
In
Computer Architecture: A Qualitative Approach
(2nd Ed. 1996) by J. L. Hennessy and D. A. Patterson, the standard textbook in this field, the disclosure of which is incorporated herein by reference, it is stated that hardware capabilities will allow ILP of several hundreds by the beginning of the next decade. Unfortunately, the same textbook also states that the main bottleneck for making this capability useful is the rather limited ability to extract sufficient ILP from current code. This has been established in many empirical studies.
SUMMARY OF THE INVENTION
The invention presents a unique computational paradigm that provides the tools to take advantage of the parallelism inherent in parallel algorithms to the full spectrum from algorithms through architecture to implementation. With the invention, programmers at the highest-level of abstraction can dictate the interthread parallelism on the instruction level and thus increase the extraction of instruction level parallelism (ILP) from code and its execution on functional units.
This explicit use of ILP throughout the various levels of programming simplifies the hardware needed to extract ILP. Moreover, it brings the concepts of a high-level language down to an instruction code language. As a result, parallel computing becomes much more like serial computing where code in high-level languages (e.g., C) resembles instruction code.
The above and other advantages of the invention are derived by providing a new instruction set architecture that extends the standard instruction set of the conventional uniprocessor architecture. New instructions added to the existing instruction set but used for the new processing elements described herein may be used on an instruction code level, as well as through the algorithmic level to make explicit the interthread parallelism in a given program.
The architecture used to implement this new computational paradigm includes a thread control unit (TCU), a spawn control unit (SCU), and an enabled instruction (EI) memory. Multiple threads are initiated and executed in parallel. Control of the threads is provided such that the threads may be suspended or allowed to execute at their own pace irrespective of their order provided the semantics of the code allow. Such independence of order semantics results in an architecture that is engineered to cope with irregular or unpredictable flows of program execution that may occur due to dynamically varying amounts of parallelism.
The invention provides new architectural tools for expressing ILP in an interthread manner without requiring simultaneous progression on all parallel threads and permitting suspension of the threads.


REFERENCES:
patent: 5050070 (1991-09-01), Chastain et al.
patent: 5151991 (1992-09-01), Iwasawa et al.
patent: 5557747 (1996-09-01), Rogers et al.
patent: 5666524 (1997-09-01), Kunkel et al.
patent: 5771382 (1998-06-01), Wang et al.
patent: 5812811 (1998-09-01), Dubey et al.
patent: WO 98/43193 (1998-10-01), None

Affiliated with

Also associated with

Rating

Spawn-join instruction set architecture for providing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Spawn-join instruction set architecture for providing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spawn-join instruction set architecture for providing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2921945