Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-12-16
2001-04-03
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S204000, C712S214000
Reexamination Certificate
active
06212542
ABSTRACT:
BACKGROUND
1. Technical Field
The technical field of the present specification relates in general to a method and system for data processing and in particular to a method and system for multiscalar data processing.
2. Description of the Related Art
In the development of data processing systems, it became apparent that the performance capabilities of a data processing system could be greatly enhanced by permitting multiple instructions to be executed simultaneously. From this realization, several processor paradigms were developed that each permit multiple instructions to be executed concurrently.
A superscalar processor paradigm is one in which a single processor is provided with multiple execution units that are capable of concurrently processing multiple instructions. Thus, a superscalar processor may include an instruction cache for storing instructions, at least one fixed-point unit (FXU) for executing fixed-point instructions, a floating-point unit (FPU) for executing floating-point instructions, a load/store unit (LSU) for executing load and store instructions, a branch processing unit (BPU) for executing branch instructions, and a sequencer that fetches instructions from the instruction cache, examines each instruction individually, and opportunistically dispatches each instruction, possibly out of program order, to the appropriate execution unit for processing. In addition, a superscalar processor typically includes a limited set of architected registers that temporarily store operands and results of processing operations performed by the execution units. Under the control of the sequencer, the architected registers are renamed in order to alleviate data dependencies between instructions.
State-of-the-art superscalar processors afford a performance of between 1 and 2 instructions per cycle (IPC) by, among other things, permitting speculative execution of instructions based upon the dynamic prediction of conditional branch instructions. Because superscalar processors have no advance knowledge of the control flow graph (CFG) (i.e., the control relationships linking basic blocks) of a program prior to execution, IPC performance is necessarily limited by branch prediction accuracy. Thus, increasing the performance of the superscalar paradigm requires not only improving the accuracy of the already highly accurate branch prediction mechanism, but also supporting a broader instruction issue bandwidth, which requires exponentially complex sequencer circuitry to analyze instructions and resolve instruction dependencies and antidependencies. Because of the inherent difficulty in overcoming the performance bottlenecks of the superscalar paradigm, the development of increasingly aggressive and complex superscalar processors has a diminishing rate of return in terms of IPC performance.
An alternative processing paradigm is that provided by parallel and multiprocessing data processing systems, which although having some distinctions between them, share several essential characteristics. Parallel and multiprocessor data processing systems, which each typically comprise multiple identical processors and are therefore collectively referred to hereinafter as multiple processor systems, execute programs out of a shared memory accessible to the processors across a system bus. The shared memory also serves as a global store for processing results and operands, which are managed by a complex synchronization mechanism to ensure that data dependencies and antidependencies between instructions executing on different processors are resolved correctly. Like superscalar processors, multiple processor systems are also subject to a number of performance bottlenecks.
A significant performance bottleneck in multiple processor systems is the latency incurred by the processors in storing results to and retrieving operands from the shared memory across the system bus. Accordingly, in order to minimize latency and thereby obtain efficient operation, compilers for multiple processor systems are required to divide programs into groups of instructions (tasks) between which control and data dependencies are identified and minimized. The tasks are then each assigned to one of the multiple processors for execution. However, this approach to task allocation is not suitable for exploiting the instruction level parallelism (ILP) inherent in many algorithms. A second source of performance degradation in multiple processor systems is the requirement that control dependencies between tasks be resolved prior to the dispatch of subsequent tasks for execution. The failure of multiple processor systems to provide support for speculative task execution can cause processors within the multiple processor systems to incur idle cycles while waiting for inter-task control dependencies to be resolved. Moreover, the development of software for multiple processor systems is complicated by the need to explicitly encode fork information within programs, meaning that multiple processor code cannot be easily ported to systems having diverse architectures.
Recently, a new aggressive “multiscalar” paradigm, comprising both hardware and software elements, was proposed to address and overcome the drawbacks of the conventional superscalar and multiple processor paradigms described above. In general, the proposed hardware includes a collection of processing units that are each coupled to a sequencer, an interconnect for interprocessor communication, and a single set of registers. According to the proposed multiscalar paradigm, a compiler is provided that analyzes a program in terms of its CFG and partitions a program into multiple tasks, which comprise contiguous regions of the dynamic instruction sequence. In contrast to conventional multiple processor tasks, the tasks created by the multiscalar compiler may or may not exhibit a high degree of control and data independence. Importantly, the compiler encodes the details of the CFG in a task descriptor within the instruction set architecture (ISA) code space in order to permit the sequencer to traverse the CFG of the program and speculatively assign tasks to the processing units for execution without examining the contents of the tasks.
According to the proposed multiscalar paradigm, register dependencies are resolved statically by the compiler, which analyzes each task within a program to determine which register values each task might possibly create during execution. The compiler then specifies the register values that might be created by each task within an associated register reservation mask within the task descriptor. The register reservations seen by a given task are the union of the register reservation masks associated with concurrently executing tasks that precede the given task in program order. During execution of the program, a processing unit executing an instruction dependent upon a register value that might be created by a concurrently executing task stalls until the register value is forwarded or the reservation is released by the preceding task. Upon release of the register or receipt of a forwarded register value by the stalled processing unit, the reservation for the register is cleared within the register reservation mask of the stalled processing unit and the stalled processing unit resumes execution. In order to trigger the forwarding of register values, the compiler adds tag bits to each instruction within a task. The tag bits associated with the last instruction in a task to create a particular register value indicate that the register value is to be forwarded to all concurrently executing tasks subsequent to the task in program order. Release of a register, on the other hand, is indicated by a special release instruction added to the base ISA or created by overloading an existing instruction within the ISA.
In contrast to register dependencies, the proposed multiscalar paradigm does not attempt to statically resolve memory dependencies and permits load and store instructions to be executed speculatively. A dynamic check must then be made to ensure that no preced
Kahle James A.
Mallick Soummya
McDonald Robert G.
Swarthout Edward L.
Banankhah Majid
Felsman Bradley Vaden Gunter & Dillon, LLP
International Business Machines - Corporation
Salys Casimer K.
LandOfFree
Method and system for executing a program within a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for executing a program within a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for executing a program within a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494069