by Jurij Silc, Borut Robic, and Theo Ungerer
Keywords: parallel computer architectures, data-driven computing, multithread computing, static dataflow, tagged-token dataflow, threaded dataflow, cycle-by-cycle interleaving, block interleaving, multithreaded superscalar
In multiprocessor systems, two main issues must be addressed: memory latency, which is the time that elapses between issuing a memory request and receiving the corresponding response, and synchronization, which is the need to enforce the ordering of instruction executions according to their data dependencies. The two issues cannot be properly resolved in a von Neumann context since connecting von Neumann processors into a very high speed general purpose computer also brings bottleneck problems [20].
As an alternative, the dataflow model was introduced as the radically new model capable of properly satisfying the two needs [8, 17, 66, 88]. Dataflow models use dataflow program graphs to represent the flow of data and control. Synchronization is achieved by a requirement that two or more specified events occur before an instruction is eligible for execution [191]. For example, in the graph/heap model [65] an instruction is enabled by the presence of simple tokens (i.e., data packets) on the arcs of copies of the dataflow graph, whereas the unraveling interpreter model (U-interpreter) [19] enables instructions by matching tags that identify the graph instance to which a token belongs. In [158] a detailed implementation of an unraveling dataflow interpreter of the Irvine Dataflow (Id) programming language is proposed. Dataflow models have also guided the design of several multithreaded computers [70].
Unfortunately, direct implementation of computers based on a pure dataflow model has been found to be an arduous task. For this reason, the impact of the convergence of the dataflow and control-flow was investigated [16, 125, 127, 141, 169]. In particular, Nikhil and Arvind posed the following question: ``What can a von Neumann processor borrow from dataflow to become more suitable for a multiprocessor?'' and offered the answer in terms of the P-RISC (Parallel RISC) programming model [164]. The model is based on a simple, RISC-like instruction set extended with three instructions that give a von Neumann processor a fine-grained dataflow capability [16]. It uses explicit fork and join commands. Based on P-RISC programming model a multithreaded Id programming language is implemented [162, 163]. Another model designed to support nested functional languages using sequential threads of instructions is the Multilisp model [114, 115, 116, 146]. Multilisp is an extension of the Lisp dialect Scheme with additional operators and semantics to deal with parallel execution. The principal language extension provided by Multilisp is future(x). Upon executing future(x), an immediate undetermined value is returned. The computation of x occurs in parallel and the result replaces undetermined when complete. Of course, any use of the result would block the parent process until the computation is finished.
The incorporation of conventional control-flow thread execution into the dataflow approach resulted in the multithreaded computer architecture which is one of the most promising and exciting avenues for the exploitation of parallelism [10, 43, 87, 128, 151, 159].
In a dataflow architecture the program execution is in terms of receiving, processing and sending out tokens containing some data and a tag. Dependencies between data are translated into tag matching and transformation, while processing occurs when a set of matched tokens arrives at the execution unit. The instruction which has to be fetched from the instruction store (according to the tag information) contains information about what to do with the data and how to transform the tags. The matching and execution unit are connected by an asynchronous pipeline, with queues added to smooth out load variations [136]. Some form of associate memory is required to support token matching. It can be a real memory with associative access, a simulated memory based on hashing, or a direct matched memory. Each solution has its proponent but none is absolutely suitable.
Due to its elegance and simplicity, the pure dataflow model has been the subject of many research efforts. Since the early 1970s, a number of dataflow computer prototypes have been built and evaluated, and different designs and compiling techniques have been simulated [17, 66, 88, 151, 168, 185, 196, 205, 208, 216, 219]. Clearly, an architecture supporting the execution of dataflow graphs should support the flow of data. Depending on the way of handling the data, several types of dataflow architectures emerged in the past [15]: single-token-per-arc dataflow [72], tagged-token dataflow [23, 229], and explicit token store [171]. We describe them in the following subsections.
The major advantage of the single-token-per-arc dataflow model is its simplified mechanism for detecting enabled nodes. Unfortunately, this model of dataflow has a number of serious drawbacks [15]. Since consecutive iterations of a loop can only partially overlap in time, only a pipelining effect can be achieved and thus a limited amount of parallelism can be exploited. Another undesirable effect is that token traffic is doubled. There is also a lack of support for programming constructs essential to any modern programming language. Despite these shortcomings, several machines were constructed and the most important are listed below. They made a tremendous impact on the field of computer architecture by introducing radically new ways of thinking about massively parallel computers. They also served as a basis for subsequent dataflow computers.
MIT Static Dataflow Architecture: This machine was designed at the Massachusetts Institute of Technology (MIT) (Cambridge, Ma, USA) [66, 67, 69, 72] as a direct implementation of a single-token-per-arc dataflow model. It consisted of five major subsystems: a memory section, a processing section, an arbitration network, a control network, and a distribution network. All communication between subsystems was by asynchronous packet transmission over the channels. A prototype was built consisting of eight processing elements (emulated by microprogrammable microprocessors) and an equidistant packet routing network using 2 X 2 routing elements; it was used primarily as an engineering model [71].
LAU System: Researchers at the CERT, Toulouse (France) carried out the first research effort to go through the entire process of graph, language, and machine design. Their system, called LAU [49, 50, 175, 211], was build in 1979. ``Language à assignation unique'' (LAU) is a French acronym for single-assignment computation. The LAU system used static graphs and had its own dataflow language based on single-assignment.
TI's Distributed Data Processor: The Distributed Data Processor (DDP)[51, 52] was a system designed by Texas Instruments (USA) aimed to investigate the potential of dataflow as the basis of a high-performance computer. The DDP was not commercially exploited, but a follow-on design with Ada as the programming language [102] had application in military systems.
DDM1 Utah Data Driven Machine: DDM1 [63] was a computing element of a recursively structured dataflow architecture designed at the University of Utah (Salt Lake City, Ut, USA) and was completed at Burroughs Interactive Research Center (La Jolla, Ca, USA). The machine organization was based on the concept of recursion. It was tree structured, with each computing element connected to a superior element (above) and up to eight inferior elements (below). Each processing element consisted of an agenda queue, which contained firable instructions, an atomic memory (providing the program memory), and an atomic processor.
NEC Image Pipelined Processor: NEC Electronics (Japan) has developed the first dataflow VLSI microprocessor chip uPD7281 [47, 133, 134, 213, 214]. Its architecture was a pipeline with several blocks, or working areas, organized in a loop. A link table and function table stored object code, while the data memory was used for temporary storage of the tokens to be matched. The address generator and flow controller matched two tokens, which were temporarily stored in the queue before they were processed by the processing unit.
Hughes Dataflow Multiprocessor: The Hughes Dataflow Multiprocessor (HDFM) project began in 1981 at Hughes Aircraft Co. (USA), prompted by the need for high performance, reliable, and easily programmable processors for embedded systems. The HDFM [42, 89, 225, 226] consisted of many, relatively simple, identical processing elements connected by a global packet-switching network. The interconnection (3-D bussed cube) network was integrated with the processing element for ease of expansion and minimization of VLSI chip types. The communications network was designed to be reliable, with automatic retry on garble messages, distributed bus arbitration, alternate path packet routing, and failed processing element translation table to allow rapid switch-in and use of spare processing elements. The communication network was able to physically accommodate up to an 8 X 8 X 8 configuration or 512 processing elements. Candidates proposed for the HDFM network were evaluated in [81]: a 3-D bussed cube network, a multi-stage network, a hypercube network, a mesh network, and a ring network. The processor engine was a three-stage pipelined processor with three operations overlapped: instruction fetch and dataflow firing rule check, instruction execution, and result and destination address combining to form a packet.
The major advantage of the tagged-token dataflow model is the higher performance it obtains by allowing multiple tokens on an arc. One of the main problems of tagged-token dataflow model was the efficient implementation of the unit that collects tokens with matching colors. For reasons of performance, an associative memory would be ideal. Unfortunately, it would not be cost-effective since the amount of memory needed to store tokens waiting for a match tends to be very large. Therefore, all existing machines use some form of hashing techniques which are typically not fast enough compared with associative memory. In what follows, we list the most important tagged-token dataflow projects.
Manchester Dataflow Computer: The researchers at the University of Manchester focused on the construction of a prototype dataflow computer [28, 29, 38, 44, 45, 92, 107, 108, 109, 110, 111, 112, 129, 184, 218, 229, 230]. The graph structure in this machine was static with token labels to keep different procedure calls separate. The machine was first implemented as a simulation program in 1977/78, and as the hardware prototype in 1981. It consisted of a single processing element and a single structure storage module connected together via a simple 2 X 2 switch. The processing element had pipelined internal structure [59], with tokens passing through a queue module, a matching unit [60] and an instruction fetch unit before being processed by one of 20 function units in a parallel array that provided the computational power. The function units were microcoded, and different instructions took quite different times to execute. To overcome the restriction in the Manchester machine that only two successor instructions could be specified in one instruction, the TUPlicate operator (iterative instruction) was introduced [36, 37]. Using TUPlicate operator reduced the size of code and led to a significant reduction in execution time especially for large programs. The Extended Manchester Dataflow Computer (EXMAN) from Indian Institute of Science (Bangalore, India) [174] incorporated three major extensions to the basic machine: a multiple matching units scheme, an efficient implementation of the array data structure, and a facility to concurrently execute reentrant routines. To allow all storage functions to be performed concurrently also a prototype parallel structure store was developed [139].
MIT Tagged-Token Dataflow Machine: This project originated at the University of California at Irvine (Ca, USA) and continued at MIT. The Irvine dataflow machine [21, 98, 99] implemented a version of the U-interpreter [97] and array handling mechanisms to support I-structure concepts [20, 23, 24, 157]. An I-structure may be viewed as a repository for data values obeying the single-assignment principle. That is, each element of the I-structure may be written only once but it may be read any number of times. The machine was proposed to consist of multiple clusters interconnected by a token ring. Each cluster (four processing elements [22]) shared a local memory through a local bus and a memory controller. The MIT machine [17, 90] was a modified Irvine machine, but still based on the Id language. Instead of using a token ring, an N X N packet switch network for interprocessor communications was used.
SIGMA-1: The SIGMA-1 [121, 122, 193, 232] system is a supercomputer for large-scale numerical computation and has been operational since early 1988 at the Electrotechnical Laboratory (Tsukuba, Japan). It consists of 128 processing elements and 128 structure elements interconnected by 32 local networks (10 X 10 crossbar packet switches) and one global two-stage Omega network. Sixteen maintenance processors are also connected with the structure elements and with a host computer for I/O operations, system monitoring, performance measurements, and maintenance operations [120].
PATTSY Processor Array Tagged-Token System: PATTSY [160] was an experimental system that had been developed at the University of Queensland (Brisbane, Australia), which supported the dynamic model of dataflow execution. PATTSY had a host computer that provided the user-interface to the machine and accepted user programs which it converted into dataflow graph. These graph were mapped onto the processing elements (PEs), but the actual scheduling of operation was carried out at runtime. An 18 processor prototype of the machine was operational. It used an IBM-PC as the host and the PEs were built from Intel 8085 based single board microcomputers.
NTT's Dataflow Processor Array System: The dataflow processors array system [212] from Nippon Telephone and Telegraph (Japan) was a dynamic tagged-token design intended for large scientific calculation. A hardware experimental system Eddy [13], consisting of 4 X 4 processing elements, was built and used to test some applications.
Q-p One-Chip Data-Driven Processor: The Q-p [25, 144, 166] is specifically designed to be a one-chip functional element which is easily programmable to form various dedicated processing functions. Particular design considerations were taken to achieve high flow-rate data-streams processing capabilities. In the Q-p, a novel bi-directional elastic pipeline processing concept was introduced to implement token matching. The Q-p was developed jointly by Osaka University, Sharp, Matsushita Electric Ind., Sanyo Electric, and Mitsubishi Electric (Japan).
DDDP Distributed Data Driven Processor: The DDDP [140] from OKI Electric Ind. (Japan) had a centralized tag manager and performed token matching using a hardware hashing mechanism similar to that of the Manchester Dataflow Computer. A prototype consisting of four processing elements and one structure store connected by a ring bus achieved 0.7 MIPS.
SDFA Stateless Data-Flow Architecture: SDFA was designed at the University of Manchester and inspired by the Manchester Dataflow Computer. As its name implies, the SDFA system [204, 205] had no notion of states. There were no structure stores, and only extract-wait functionality was provided in the matching stores. All the instructions in the instruction-set were simple and based on RISC principles. There were no iterative or vector style instructions producing more than two tokens per execution.
CSIRAC II: The origins of the CSIRAC II dataflow computer date from 1978 [78]. It was built at the Swinburne Institute of Technology (Hawthorn, Australia). The architecture is unusual in that the temporal order of tokens with the same color on the same graph arc is maintained [76, 77].
PIM-D Parallel Inference Machine: The PIM-D was proposed to be one of the candidates for a parallel inference machine in the Fifth Generation Computer System and was a joint venture of ICOT and OKI Electric Ind. (Japan) [130, 131, 132]. This machine was constructed from multiple processing elements and multiple structure memories interconnected by a hierarchical network and exploited three types of parallelism: OR parallelism, AND parallelism, and parallelism in unification.
The explicit token address store principle was developed in the Monsoon project, but is applied in most dataflow architectures developed more recently (see Subsection 3.2. below), i.e. as so-called direct matching in the EM-4 and Epsilon-2.
Monsoon: The Monsoon dataflow multiprocessor was built jointly by MIT and Motorola (USA) [55, 172, 192, 217]. Monsoon dataflow processor nodes are coupled by a packet-communication network with each other and with I-structure storage units. The main objective of the Monsoon dataflow processor architecture was to alleviate the waiting/matching problem by explicitly using address token store. This is achieved by a dataflow processor using an eight-stage pipeline. The first pipeline stage is the instruction fetch stage which is arranged prior to the token matching, in contrast to dynamic dataflow processors with associative matching units. The new arrangement is necessary, since the operand fields in an instruction denote the offset in the memory frame that itself is addressed by the tag of a token. The explicit token address is computed by the composition of frame address and operand offset. This is done in the second stage, which is the first of three pipeline stages that perform the token matching. In the third stage a presence bit store access is performed to find out if the first token of a dyadic operation has already arrived. If that is not the case, the presence bit is set and the current token is stored of the frame slot in the frame store in the fourth stage. Otherwise the presence bit is reset and the operand retrieved from the frame store in the fourth pipeline stage. The next three stages are execution stages in the course of which the next tag is also computed concurrently. The eighth stage forms one or two new tokens that are sent to the network, stored in a user token queue, a system token queue, or directly recirculated to the instruction fetch stage of the pipeline (see next section). Several small Monsoon systems have been built and installed at universities and research institutes.
Fig. 2.1 - Computing ab + a/c with: (a) control flow; (b) dataflow. Pure dataflow basic execution pipeline: (c) single-token-per-arc dataflow; (d) tagged-token dataflow; (e) explicit token store dataflow.
Since a context switch occurs in fine-grain dataflow after each instruction execution, no use of registers is possible. Use of registers could optimize the access time to data values, avoid pipeline bubbles caused by dyadic instructions, and reduce the total number of tokens during program execution.
One solution of these problems is combining the dataflow and control-flow mechanisms. The symbiosis between dataflow and von Neumann architectures is represented by a number of research projects developing von Neumann/dataflow hybrids [41, 127]. The spectrum of such hybrids is very broad, ranging from simple extensions of a von Neumann processor with a few additional instructions to specialized dataflow systems attempting to reduce overhead by increasing the execution grain size and employing various scheduling, allocation, and resource management techniques developed for von Neumann computers. These developments illustrate that dataflow and von Neumann computers do not necessarily represent two entirely disjoint worlds but rather are the two extreme ends of a spectrum of possible computer systems (Fig. 3.1 a,b,c).
After early hybrid dataflow attempts, several techniques for combining control-flow and dataflow have emerged: threaded dataflow [173], large-grain dataflow [127], RISC dataflow [164], and dataflow with complex machine operations [80]. We describe them in the next five subsections (for a comparison of the techniques see [31]).
JUMBO Newcastle Data-Control Flow Computer: The JUMBO [220] was built at the University of Newcastle upon Tyne (England) to study the integration of dataflow and control-flow computation. It has a packet communication organization with token matching. There are three principal units (matching unit, memory unit, processing unit) interconnected into ring by FIFO buffers.
MADAME Macro Dataflow Machine: The MADAME architecture from Jozef Stefan Institute (Ljubljana, Slovenia) was suitable for execution of acyclic dataflow (sub)graphs and supported synchronous dataflow computing [197, 198, 199, 200]. The advantage of such computing over pure dataflow is that more efficient runtime code can be generated because instructions can be scheduled at compile-time rather than at runtime.
PDF Piecewise Dataflow Architecture: The PDF architecture addressed Lawrence Livermore National Laboratory's (Livermore, Ca, USA) needs for supercomputing power. This architecture [177, 178] blended the strengths found in SIMD, MIMD, and dataflow architectures. The PDF contained a SIMD processing unit and a scalar processing unit that managed a group of processors (MIMD). Programs that ran on the PDF were broken into basic blocks and scheduled for execution using dataflow techniques. Two levels of scheduling divided responsibility between the software and hardware. The time-consuming analysis of when blocks can overlap was done in the compile-time, before program executions began. Individual instruction scheduling was done in hardware.
MUSE Multiple Stream Evaluator: The MUSE machine [40] from University of Nottingham (England) was a structured architecture supporting both serial and parallel processing which allowed the abstract structure of a program to be mapped onto the machine in a logical way. The MUSE machine had many features of dataflow architecture but in its detailed operation it steered a middle course between a pure dataflow machine, a tree machine, and the graph reduction approach.
RAMPS Real Time Acquisition and Multiprocessing System: RAMPS [30] was a parallel processing system developed at EIP Inc. (USA) for high performance data acquisition and processing applications. RAMPS used dataflow at a macro level while tasks were executed using a sequential model of computation.
DTN Dataflow Computer: The DTN Dataflow Computer [227] (developed by the Dutch company Dataflow Technology Nederland) is a high-performance workstation well suited for applications containing relatively small computing-intensive parts with enough parallelism to execute efficiently on the dataflow engine. The DTN Dataflow Computer contains a standard general purpose host, a graphical subsystem (four microprogrammable systolic arrays), and a dataflow engine. The dataflow engine consists of eight identical modules connected by a token routing network. Each module contains four NEC Image Pipelined Processors, interface chip, and image memory.
ETCA Functional Dataflow Architecture: A functional dataflow architecture has been developed at ETCA (Arcueil, France) and is dedicated to real-time processing [190]. Two types of data-driven processing elements, dedicated respectively to low and mid-level processing are integrated in a regular 3-D array. Its design relies on close integration of dataflow principles and functional programming. For the execution of low-level functions, a custom dataflow processor with six bi-directional I/O ports was developed [176].
Monsoon: The Monsoon dataflow processor can be viewed as a cycle-by-cycle interleaving multithreaded computer [173] due to its ability of direct token recycling. By use of this technique a successor token is directly fed back in the eight-stage Monsoon pipeline bypassing the token store. Another instruction of the same thread is executed every eighth processor cycle. Monsoon allows the use of registers (eight register sets are provided) to store intermediate results within a thread, thereby leaving the pure dataflow execution model.
Epsilon-2: Epsilon-2 machine [100, 101] developed at Sandia National Laboratories (Livermore, Ca, USA), supports a fully dynamic memory model, allowing single cycle context switches and dynamic parallelization. The system is built around a module consisting of a processor and structure unit, connected via a 4 X 4 crossbar to each other, an I/O port, and the global interconnect. The structure unit is used for storing data structures such as arrays, lists, and I-structures. The Epsilon-2 processor retains the high performance features of the Epsilon-1 prototype, including direct matching, pipelined processing, and a local feedback path. The ability to execute sequential code as a grain provides RISC-like execution efficiency.
EM-4 and EM-X: In the EM-4 project [35, 142, 181, 182, 183, 186, 187, 188, 189, 206] at Electrotechnical Laboratory (Tsukuba, Japan), the essential elements of a dynamic dataflow architecture using frame storage for local variables are incorporated into a single chip processor. In this design a strongly connected subgraph of a function body is implemented as a thread that uses registers for intermediate results. The EM-4 was designed for 1024 nodes. Since May 1990 the EM-4 prototype with 80 nodes (EMC-R gate-array processor) is operational. In 1993 the EM-X [143] (upgrade of EM-4) was designed to support latency reduction by fusing the communication pipeline with the execution pipeline, latency hiding via multithreading, and runtime latency minimization for remote memory access.
TAM Threaded Abstract Machine: The TAM [54, 56] from the University of California (Berkeley, Ca, USA) is an execution model for fine-grain interleaving of multiple threads, that is supported by an appropriate compiler strategy and program representation instead of elaborate hardware. TAM's key features are placing all synchronization, scheduling, and storage management under explicit compiler control.
*T: The *T (pronounced ``start'' [165]) is a direct descendant of dataflow architectures, especially of the Monsoon, and unifies them with von Neumann architectures. *T has a scalable computer architecture designed to support a broad variety of parallel programming styles including those which use multithreading based on non-blocking threads. A *T node consists of the data processor (executing threads), the remote-memory request coprocessor (for incoming remote load/store requests), and the synchronization coprocessor (for handling returning load responses and join operations), which all share local memory. This hardware is coupled with a high performance network having a fat-tree topology with high cross-section bandwidth. A modified version of the *T [165] was implemented in cooperation by MIT and Motorola, based on a 88110 superscalar microprocessor (called 88110MP [32, 33]). Despite its name the StarT-ng [14, 46] bears no resemblance to its predecessor *T and to dataflow machines. It defines a rather conventional multiprocessor with PowerPC 620 processors augmented with special hardware for message-passing and shared memory access.
ADARC Associative Dataflow Architecture: In the Associative Dataflow Architecture ADARC [209, 210, 233] the processing units are connected via an associative communication network. The processors are equipped with private memories that contain instruction sequences generated at compile-time. The retrieval of executable instructions is replaced by the retrieval of input operands for the current instructions from the network. The structure of the network enables full parallel access to all previously generated results by all processors. A processor executes its current instruction (or instruction sequence) as soon as all requested input operands have been received [209]. In [233] it is shown that that ADARC is well-suited to implement neural network models. ADARC was developed at J.W.Goethe University (Frankfurt, Germany).
Pebbles: The Pebbles architecture [180] from Colorado State University (Fort Collins, Co, USA) is a large-grain dataflow architecture with a decoupling of the synchronization unit and the execution unit within the processing elements. The processing elements are coupled via a high-speed network. The local memory of each node consists of an instruction memory which is read by the execution unit and a data memory (or frame store) which is accessed by the synchronization unit. A ready queue contains the continuations representing those threads that are ready to execute. The frame store is designed as a storage hierarchy where a frame cache holds the frames of threads that will be executed soon. The execution unit is a 4-way superscalar microprocessor.
From Argument Fetch Dataflow Processor to MTA and EARTH: The EARTH (Efficient Architecture of Running Threads) [155], developed at McGill University and Concordia University (Montreal, Canada), is based on the MTA (Multithreaded Architecture) [86, 126] and dates back to the Argument Fetch Dataflow Processor. An MTA node consists of an execution unit that may be an off-the-shelf RISC microprocessor and a synchronization unit to support dataflow-like thread synchronization. The synchronization unit determines which threads are ready to be executed. Execution unit and synchronization unit share the processor local memory which is cached. Accessing data in a remote processor requires explicit request and send messages. The synchronization unit and execution unit communicate via FIFO queues: a ready queue containing ready thread identifiers links the synchronization unit with the execution unit, and an event queue holding local and remote synchronization signals connects the execution unit with the synchronization unit, but also receives signals from the network. A register use cache keeps track of which register set is assigned to which function activation [126]. MTA or EARTH rely on non-blocking threads. The EARTH architecture [161] is implemented on top of the experimental (but rather conventional) MANNA multiprocessor [91].
P-RISC Parallel RISC: The basic philosophy underlying the development of the P-RISC architecture [164] can be characterized as follows: use a RISC-like instruction set, change the architecture to support multithreaded computation, add fork and join instructions to manage multiple threads, implement all global storage as I-structure storage, and implement the load/store instructions to execute in split-phase mode (Fig. 3.1 d,e). The architecture based on the above principles was developed at MIT. It consists of a collection of PEs and Heap Memory Elements, interconnected through a packed-switching communication network.
Decoupled Graph/Computation Architecture: In this architecture, developed at the University of Southern California (Los Angeles, Ca, USA), the token matching and token formatting and routing are reduced to a single graph operation called determine executability [80]. The decoupled graph/computation model separates the graph portion of the program from the computational portion. The two basic units of the decoupled model ( computational unit and graph unit) operate in an asynchronous manner. The graph unit is responsible for determining executability by updating the dataflow graph, while the computation unit performs all the computational operations (fetch and execute).
Stollman Data Flow Machine: The Stollman dataflow machine [95, 96] from Stollman GmbH (Hamburg, Germany) is a coarse-grain dataflow architecture directed towards database applications. The dataflow mechanism is emulated on a shared-memory multiprocessor. The query tree of a relational query language (such as the database query language SQL) is viewed as dataflow graph. Complex database query instructions are implemented as coarse-grain dataflow instruction and (micro-)coded as a traditional sequential program running on the emulator hardware.
ASTOR Augsburg Structure-Oriented Architecture: The ASTOR architecture [223, 224, 234, 235] from University of Augsburg (Germany) can be viewed as a dataflow architecture that utilizes task level parallelism by the architectural structure of a distributed memory multiprocessor, instruction level parallelism by a token-passing computation scheme, and subinstruction level parallelism by SIMD evaluation of complex machine instructions. Sequential threads of data instructions are compiled to dataflow macro actors and executed consecutively using registers. A dependency construct describes the partial order in the execution of instructions. It can be visualized by a dependency graph. The nodes in a dependency graph represent control constructs or data instructions; the directed arcs denote control dependencies between the nodes. Tokens are propagated along the arcs of the dependency graph. To distinguish different activations of a dependency graph, a tag is assigned to each token. The firing rule of dynamic dataflow is applied: a node is enabled as soon as tokens with identical tags are present on all its input arcs. However, in the ASTOR architecture tokens do not carry data.
Fig. 3.1 - Spectrum of scheduling models: (a) fully ordered (control flow); (b) partially ordered (dataflow); (c) partially ordered graph and fully ordered grains (e.g. Epsilon-2 hybrid). ``RISCifying'' dataflow (P-RISC dataflow/von Neumann hybrid): (d) conceptual; (e) encoding of graph.
Fig. 4.1 - Multithreading: when a thread issues a remote-load request, the processor starts executing another thread.
Another notion is the distinction between blocking and non-blocking threads. A non-blocking thread is formed such that its evaluation proceeds without blocking the processor pipeline (for instance by remote memory accesses, cache misses or synchronization waits). Evaluation of a non-blocking thread starts as soon as all input operands are available, which is usually detected by some kind of dataflow principle. Thread switching is controlled by the compiler harnessing the idea of rescheduling rather than blocking when waiting for data. Access to remote data is organized split-level by one thread sending the access request to memory and another thread activating when its data is available. Thus a program is compiled into many very small threads activating each other when data become available. The same hardware mechanisms may also be used to synchronize interprocess communications to awaiting threads, thereby alleviating operating systems overhead [159]. In contrast, a blocking thread might be blocked during execution caused by remote memory accesses, cache misses or synchronization needs. The waiting time, during which the pipeline is blocked, is lost when using a von Neumann processor, but can be bridged by a fast thread switch in a multithreaded processor. The thread is resumed when the reason for blocking is removed. Use of non-blocking threads typically leads to many small threads that are appropriate for execution by a hybrid dataflow computer or by a multithreaded architecture that is closely related to hybrid dataflow. Blocking threads may be normal threads or whole processes of a multithreaded UNIX-based operating system.
Notice, that we exclude in this section architectures that are designed for the execution of non-blocking threads. Although these architectures often are called multithreaded, we categorized them as threaded dataflow (Subsection 3.2.) or large-grain dataflow (Subsection 3.3.) since a dataflow principle is applied to start execution of non-blocking threads. Thus, multithreaded architectures (in the more narrow sense applied here) stem from the modification of RISC or even of superscalar RISC processors. They are able to bridge waiting times that arise in the execution of blocking threads by fast thread switching. This ability is in contrast to RISC processors or today's superscalar processors, that use busy waiting or a time-consuming, operating system based thread switch. One characteristic for such multithreaded architectures is the use of multiple register sets and a mechanism that dynamically triggers the thread switch. Thread switch overhead must be very low, from zero to only a few cycles.
Current microprocessors utilize instruction-level parallelism by a deep processor pipeline and by the superscalar instruction issue technique. A superscalar processor is able to dispatch multiple instructions each clock cycle from a conventional linear instruction stream [73]. DEC Alpha 21164, IBM & Motorola PowerPC 604 and 620, MIPS R10000, Sun UltraSparc and HP PA-8000 issue up to four instructions per cycle from a single thread. VLSI-technology will allow future generations of microprocessors to exploit instruction-level parallelism up to 8 instructions per cycle, or more.
However, the instruction-level parallelism found in a conventional instruction stream is limited. Recent studies showed the limits of processor utilization even of today's superscalar microprocessors. Using the SPEC92 benchmark suite, the PowerPC 620 showed an execution of 0.96 to 1.77 instructions per cycle [74], and even an 8-issue Alpha processor will fail to sustain 1.5 instructions per cycle [222].
The solution is the additional utilization of more coarse-grained parallelism. The main approaches are the multiprocessor chip and the multithreaded processor. The multiprocessor chip integrates two or more complete processors on a single chip. Therefore every unit of a processor is duplicated and used independently of its copies on the chip. In contrast, the multithreaded processor stores multiple contexts in different register sets on the chip. The functional units are multiplexed between the threads that are loaded in the register sets. Depending on the specific multithreaded processor design, only a single instruction pipeline is used, or a single dispatch unit issues instructions from different instruction buffers simultaneously. Because of the multiple register sets, context switching is very fast. Multithreaded processors tolerate memory latencies by overlapping the long-latency operations of one thread with the execution of other threads - in contrast to the multiprocessor chip approach. While the multiprocessor chip is easier to implement, use of multithreading in addition to a wide issue bandwidth is a promising approach.
Research on multithreaded architectures has been motivated by two concerns: tolerating latency and bridging of synchronization waits by rapid context switches. Three different approaches of multithreaded architectures are distinguished: cycle-by-cycle interleaving [117, 173, 202, 215], block interleaving [2, 3, 106], and simultaneous multithreading [221, 222].
HEP Heterogeneous Element Processor: The HEP system was a MIMD shared-memory multiprocessor system developed by Denelcor Inc. (Denver, Co, USA) between 1978 and 1985 137, 145, 201, 202, 203], and was a pioneering example of a multithreaded machine. Spatial switching occurred between two queues of processes, one of these controlled program memory, register memory, and the functional memory while the other controlled data memory. The main processor pipeline had eight stages, matching the number of processor cycles necessary to fetch a data item from memory in register. Consequently eight threads were in execution concurrently within a single HEP processor. In contrast to all other cycle-by-cycle interleaving processor, all threads within a HEP processor shared the same register set. Multiple processors and data memories were interconnected via a pipelined switch and any register memory or data memory location could be used to synchronize two processes on a producer-consumer basis by a full/empty bit synchronization on a data memory word.
MASA Multilisp Architecture for Symbolic Applications: The MASA was a multithreaded processor architecture for parallel symbolic computation with various features intended for effective Multilisp program execution [85, 117]. MASA featured a tagged architecture, multiple contexts, fast trap handling, and a synchronization bit in every memory word. Its principal novelty was the use of multiple contexts both to support interleaved execution from separate instruction streams and to speed up procedure calls and trap handling (in the same manner as register windows).
Horizon: This (paper) architecture was based on the HEP but extended to a massively parallel MIMD computer. The machine was designed for up to 256 processing elements and up to 512 memory modules in a 16 X 16 X 6 node internal network. Like HEP it employed a global address space, and memory-based synchronization through the use of full/empty bits at each location [94, 148, 215]. Each processor supported 128 independent instruction streams by 128 register sets with context switches occurring at every clock cycle.
Tera MTA Multi-Threaded Architecture: The Tera MTA [9, 11, 12] is based on the Horizon architecture and currently under construction by Tera Computer Company (Seattle, Wa, USA) (after many delays introduction to market is scheduled for Spring 1997). The machine is a vast multiprocessor with multithreaded processor nodes arranged in 3D mesh of pipelined packet-switch nodes. In the case of the maximum configuration of 4096 nodes, arranged in a 16 X 16 X 16 mesh, there are up to 256 processors, 512 memory units, 256 I/O cache units, 256 I/O processors, and 2816 switching nodes. Each processor is 64-bit custom chip with up to 128 simultaneous threads in execution. It alternates between ready threads, using a deep pipeline. Inter-instruction dependencies are explicitly encoded by the compiler. Each thread has a complete set of registers. Memory units have 4-bit tags on each word, or full/empty and trap bits [12]. The Tera MTA exploits parallelism at all levels, from fine-grained instruction-level parallelism within a single processor to parallel programming across processors, to multiprogramming among several applications simultaneously. Consequently, processor scheduling occurs at many levels, and managing these levels poses unique and challenging scheduling concerns [11].
SB-PRAM and HPP: The SB-PRAM [1, 26] or HPP (High Performance PRAM) [83, 84] is a MIMD parallel computer with shared address space and uniform memory access time due to its motivation: building a multiprocessor that is as close as possible to the theoretical machine model CRCW-PRAM. Processor and memory modules are connected by a butterfly network. Network latency is hidden by pipelining several so-called virtual processors on one physical processor node in cycle-by-cycle interleaving mode. A first prototype (SB-PRAM) [26] is running with four processors, a second prototype (HPP) is under construction. In the SB-PRAM 32 virtual processors are scheduled round-robin for every instruction [83]. The project is running at the University of Saarland (Saarbruecken, Germany).
In the block interleaving model a thread is executed for many cycles before context switching. Context switches are used only to hide long memory latencies since small pipeline delays are hidden by proper ordering of instructions performed by the optimizing compiler. Since multithreading is not used to hide pipeline delays, fewer total threads are needed and a single thread can execute at full speed until the next context switch. This may also simplify the hardware. There are three variations of this model. The switch-on-load version switches only on instructions that load data from shared memory while storing data in shared memory does not cause context switching (since local memory loads and other instructions all complete quickly and can be scheduled by the compiler). However, context switches sometimes occur sooner than needed: If a compiler ordered instructions so that a load from shared memory was issued several cycles before the value was used, the context switch should not have to occur until the actual use of the value. This strategy is implemented in the switch-on-use model [154]. Here, a valid bit is added to each register. The bit is cleared when the loading from shared memory to the corresponding register is issued and set when the result returns from the network. A thread context switches if it needs a value from a register whose valid bit is still cleared. A benefit of this model is that several load instructions can be grouped together thus prefetching several operands of an instruction. Instead of using valid bits, an explicit context switch instruction can be added between the group of loads and their subsequent uses. This model, which is called explicit-switch [56, 165], is simpler to implement and requires only one additional instruction.
The multithreading with caching approach adds caches to the block interleaving model. Only those loads that miss in the cache have long latencies and cause context switches. By filtering out many of the remote references, caching reduces the number of threads. In [39], it is shown that for most applications just two or three threads per processor is sufficient. There are three variations of the cache-extended block interleaving model. The switch-on-miss model [5] context switches if load from shared memory instructions misses in the cache. Such a context switch is not detected immediately, however, so a number of subsequent instructions have already entered the CPU pipeline and thus wasted CPU time. The switch-on-use-miss model [106] context switches when an instruction tries to use the (still missing) value from a shared load that missed in the cache. The conditional-switch model provides the benefits of grouping (of the explicit-switch model) and caching. In this model, the explicit switch instruction is ignored if all load instructions (in the preceding group) hit the cache; otherwise, the context switch is performed. In what follows, we describe five representatives of the block interleaving model of multithreading.
CHoPP Columbia Homogeneous Parallel Processor: The CHoPP [154] was a shared memory MIMD with up to 16 powerful computing nodes. High sequential performance is due to issuing multiple instructions on each clock cycle, zero-delay branch instructions, and fast execution of individual instructions. Each node can support up to 64 threads.
Sparcle Processor in Alewife System: The MIT Alewife multiprocessor [3, 4, 5, 6, 7, 147] is based on the multithreaded Sparcle processor. The Sparcle processor is derived from a Sparc RISC processor. The eight overlapping register windows of a Sparc processor are organized in four independent non-overlapping thread contexts, each using two windows (one as register set, the other as a context for trap and message handlers). Thread switching is triggered by external hardware when a remote memory access is detected. Emptying the pipeline from instructions of the thread that caused the context switch and organizational software overhead sum up to a context switching penalty of 14 processor cycles. The Alewife multiprocessor has been operational since May 1994 [4]. It uses a low-dimensional direct interconnection network. Despite its distributed-memory architecture, Alewife allows efficient shared-memory programming through a multilayered approach to locality management. Communication latency and network bandwidth requirements are reduced by a directory-based cache-coherence scheme referred to as LimitLESS directories. Latencies still occur although communication locality is enhanced by runtime and compile-time partitioning and placement of data and processes.
MSparc: An approach similar to the Sparcle processor is taken at the University of Oldenburg (Germany) with the MSparc processor [156, 179]. MSparc supports up to four contexts on chip and is compatible to standard Sparc processors. Switching is supported by hardware and can be achieved within one processor cycle. The multithreading policy is block interleaving with the switch-on-cache-miss policy as in the Sparcle processor.
J-Machine: The MIT Jellybean Machine [58, 167] is so called because it is to be built entirely of a large number of ``jellybean'' components. The initial version uses an 8 X 8 X 16 cube network, with possibilities of expanding to 64K nodes. The ``jellybeans'' are message driven processor (MDP) chips, each of which has a 36-bit processor, a 4K word memory, and a router with communication ports for 6 directions. External memory of up to 1 M words can be added per processor. The MDP creates a task for each arriving message. In the prototype, each MDP chip has 4 external memory chips that provide 256K memory words. However, access is through a 12-bit data bus, and with an error correcting cycle, the access time is four memory cycles per word. Each communication port has a 9-bit data channel. The routers provide support for automatic routing from source to destination. The latency of a transfer is 2 microseconds across the prototype machine, assuming no blocking. When a message arrives, a task is created automatically to handle it in 1 microsecond. Thus, it is possible to implement a shared memory model using message passing, in which a message provides a fetch address and an automatic task sends a reply with the desired data.
Rhamma: The multithreaded Rhamma processor [103, 104] from the University of Karlsruhe (Germany) uses a fast context switch to bridge latencies caused by memory accesses or by synchronization operations. Load/store, synchronization and execution operations of different threads are executed simultaneously by specialized functional units within the processor. The units are coupled by FIFO buffers and access different register sets. Each unit stops the execution of a thread when it recognizes an instruction intended for another unit. To perform a context switch the unit passes the thread tag to the FIFO buffer of the unit that is appropriate for the execution of the instruction. Then the unit resumes processing with another thread of its own FIFO buffer. The Rhamma processor is most similar to the Sparcle. However, the execution unit of the Rhamma processor switches the context whenever it comes across a load, store or synchronization instruction, and the load/store unit switches whenever it meets an execution or synchronization instruction (switch-on-load policy). In contrast to Sparcle, the context switch is in an early stage of the pipeline, thus decreasing context switching time. On the other hand, the overall performance of the Rhamma processor suffers from the higher rate of context switches unless the context switch time is very small. Software simulations showed the need for extremely fast context switching. Therefore a VHDL representation of Rhamma with optimizations towards fast context switching was developed, simulated and synthesized. Specific implementation techniques reduce switching costs to zero or at most one processor cycle. These techniques use a context switch buffer which is a table containing the addresses of instructions that already yielded a context switch.
Media Research Laboratory Processor: The multithreaded processor of the Media Research Laboratory of Matsushita Electric Ind. (Japan) [123, 124] is the first approach to simultaneous multithreading. Instructions of different threads are issued simultaneously to multiple functional units. Simulation results on a parallel ray-tracing application showed that using 8 threads a speed-up of 3.22 in case of one load/store unit and of 5.79 in case of two load/store units can be achieved over a conventional RISC processor. However, caches or TLBs are not simulated, nor is a branch prediction mechanism.
Simultaneous Multithreading: The simultaneous multithreading approach from the University of Washington (Seattle, Wa, USA) [79] surveys enhancements of the Alpha 21164 processor [222] and of a hypothetical out-of-order issue superscalar microprocessor that resembles R10000 and PA-8000 [221]. Simulations were conducted to evaluate processor configurations of an up to 8-threaded and 8-issue superscalar. This maximum configuration showed a throughput of 6.64 instructions per cycle due to multithreading using the SPEC92 benchmark suite and assuming a processor with 32 functional units (among them multiple load/store units) [222]. The second approach [221] evaluated more realistic processor configurations and reached a throughput of 5.4 instructions per cycle for the 8-threaded and 8-issue superscalar case. Implementation issues and solutions to register file access and instruction scheduling were also presented.
Multithreaded Superscalar (Sigmund & Ungerer): While the simultaneous multithreading approach [222] surveys enhancements of the Alpha 21164 processor, the multithreaded superscalar processor approach from the University of Karlsruhe [194, 195] is based on a simplified PowerPC 604 processor. Both approaches, however, are similar in their instruction issuing policy. The multithreaded superscalar processor implements the six-stage instruction pipeline of the PowerPC 604 processor (fetch, decode, dispatch, execute, complete, and write-back) [207] and extends it to employ multithreading. The processor uses various kinds of modern microarchitecture techniques as e.g. separate code and data caches, branch target address cache, static branch prediction, in-order dispatch, independent execution units with reservation stations, rename registers, out-of-order execution, and in-order completion. However the instruction set is simplified (using an extended DLX [119] instruction set instead). A software simulation evaluated various configurations of the multithreaded superscalar processor. While the single-threaded 8-issue superscalar processor only reached a throughput of about 1.14 instructions per cycle, the 8-threaded 8-issue superscalar processor executed 4.19 instructions per cycle (the load/store frequency in the work load sets the theoretical maximum to 5 instructions per cycle). Increasing the superscalar issue bandwidth from 4 to 8 yields only a marginal gain in instruction throughput - a result that is nearly independent of the number of threads in the multithreaded processor. A multiprocessor chip approach with 8 single-threaded scalar processors reaches 6.07 instructions per cycle. Using the same number of threads, the multiprocessor chip reaches a higher throughput than the multithreaded superscalar approach. However, if the chip costs are taken into consideration, a 4-threaded 4-issue superscalar processor outperforms a multiprocessor chip built from single-threaded processors by a factor of 1.8 in performance/cost relation [194].
Multithreaded Superscalar (Bagherzadeh et al.:) This multithreaded superscalar processor approach [105, 153] combines out-of-order execution within an instruction stream with the simultaneous execution of instructions of different instruction streams. A particular superscalar processor called Superscalar Digital Signal Processor (SDSP) is enhanced to run multiple threads. The enhancements are directed by the aim of minimal modification to the superscalar base processor. Therefore most resources on the chip are shared by the threads, as for instance the register file, reorder buffer, instruction window, store buffer, and renaming hardware. Based on simulations a performance gain of 20 - 55 % due to multithreading was achieved across a range of benchmarks. The project runs at the University of California at Irvine.
In the first paper on the PentiumPro, the instruction pipeline is described as [48]: ``The flow of the Intel Architecture instructions is predicted and these instructions are decoded into micro-operations (micro-ops), or series of micro-ops, and these micro-ops are register-renamed, placed into an out-of-order speculative pool of pending operations, executed in dataflow order (when operands are ready), and retired to permanent machine state in source program order.'' After register renaming the instructions (or micro-ops) are placed in an instruction window of pending instructions and in a reorder buffer that saves the program order and execution states of the instructions (instruction window and reorder buffer may coincide). State-of-the art microprocessors typically provide 32 (R10000), 40 (PentiumPro) or 56 (PA-8000) instruction slots in the instruction window or reorder buffer. Instructions are ready to be executed as soon as all operands are available. A 4-issue superscalar processor dispatches up to 4 instructions per cycle to the execution units provided that resouce conflicts do not occur. Dispatch and execution determine the out-of-order section of a microprocessor. After execution instructions are retired in program order.
Comparing dataflow computers with such superscalar microprocessors shows several similarities and differences which are briefly discussed below.
While a single thread of control in modern microprocessors often does not incorporate enough fine-grained parallelism to feed the multiple functional units of todays microprocessors, dataflow resolves any threads of control into separate instructions that are ready to execute as soon as all required operands are available. Thus, the fine-grained parallelism potentially utilized by a dataflow computer is far larger than the parallelism available for microprocessors.
Data and control dependencies potentially cause pipeline hazards in microprocesssors that are handled by complex forwarding logic. Due to the continuous context switches in fine-grain dataflow computers and in cycle-by-cycle interleaving machines, pipeline hazards are avoided with the disadvantage of a poor single thread performance.
Antidependencies and output dependencies are removed by register renaming that maps the architectural registers to the physical registers of the microprocessor. Thereby the microprocessor internally generates an instruction stream that satisfies the single assignment rule of dataflow. Modern microprocessors remove antidependencies and output dependencies on-the-fly and avoid the high memory requirements, the often awkward solutions for data structure storage and manipulation, and for loop control caused by the single assignment rule in dataflow computers.
The main difference between the dependence graphs of dataflow and the code sequence in an instruction window of a microprocessors is branch prediction and speculatively execution. The accuracy of the branch prediction is surprisingly high - more than 95 % are reported for single SPECmark programs. However, rerolling execution in case of a wrongly predicted path, is costly in processor cycles especially in deeply pipelined microprocessors. The idea of branch prediction and speculative execution has never been evaluated in the dataflow environment.
Due to the single thread of control, a high degree of data and instruction locality is present in the machine code of a microprocessor. The locality allows to employ a storage hierarchy that stores the instructions and data potentially executed in the next cycles close to the executing processor. Due to the lack of locality in a dataflow graph, a storage hierarchy is difficult to apply in dataflow computers.
The matching of executable instructions in the instruction window of microprocessors is restricted to a part of the instruction sequence. Because of the serial program order, the instructions in this window are likely to be executable soon. Therefore the matching hardware can be restricted to a small number of instruction slots. In dataflow computers the number of tokens waiting for a match can be very high. A large waiting-matching store is required. Due to the lack of locality the likelyhood of the arrival of a matching token is difficult to estimate so caching of tokens to be matched soon is difficult in dataflow.
An unsolved problem in todays microprocessors is the memory latency caused by cache misses. As reported for the SGI Origin 2000 distributed shared memory system [150] these latencies are 11 processor cycles for a primary-level cache miss, 60 cycles for a secondary-level cache miss, and can be up to 180 cycles for a remote memory access. In number of missed instruction slots the latencies should be multiplied by the degree of superscalar. Only a small part of the memory latency can be removed or hidden in modern microprocessors even when techniques like out-of-order execution, write buffer, cache preload hardware, lockup free caches, and a pipelined system bus are employed. So microprocessors often idle and are unable to exploit the high degree of internal parallelism provided by a wide superscalar approach. The rapid context switching of dataflow and multithreaded architectures shows a superior way out. Idling is avoided by switching execution to another context.
An 8-issue (or even higher) superscalar dispatch will be possible in the next generation of microprocessors. Finding enough fine-grain parallelism to fully exploit the processor will be the main problem. One solution is to enlarge the instruction window to several hundred instruction slots with hopefully more simultaneously executable instructions present. There are two draw-backs to this approach. First, regarding that all instructions stem from a single instruction stream and that on average every seventh instruction is a branch instruction, most of the instructions in the window will be speculatively assigned with a very deep speculation level (todays depth normally is four at maximum). Thereby most of the instruction execution will be speculative. The principal problem here arises from the single instruction stream that feeds the instruction window. Second, if the instruction window is enlarged, the updating of the instruction states in the slots and matching of executable instructions lead to more complex hardware logic in the dispatch stage of the pipeline thus limiting the cycle rate increase which is essential for next generations of microprocessors. Solutions are the decoupling of the instruction window with respect to different instruction classes as in the PA-8000, the partitioning of the dispatch stage into several pipeline stages, and alternative instruction window organizations. One alternative instruction window organization is the multiple FIFO-based organization in the dependence-based microprocessor [170]. Only the instructions at the heads of a number of FIFO buffers can be dispatched to the execution units in the next cycle. The total parallelism in the instruction window is restricted in favour of a less costly dispatch that does not slow down processor cycle rate. Thereby the potential fine-grained parallelism is limited - a technique somewhat similar to the threaded dataflow approaches described above. It might be interesting to look, with respect to alternative instruction window organizations, at dataflow matching store implementations and dataflow solutions like threaded dataflow as exemplified by the repeat-on-input technique in the Epsilon-2 and strongly-connected arcs model of EM-4, or the associative switching network in the ADARC, etc. For example, the repeat-on-input strategy dispatches very small compiler-generated code sequences serially (in an otherwise fine-grained dataflow computer). Transfered to the local dataflow in an instruction window, a dispatch string might be used where a serie of data dependent instructions are generated by a compiler and dispatched serially after the dispatch of the leading instruction. However, the high number of speculative instructions in the instruction window remains.
Another new idea is the nanothreading technique of DanSoft (Kosice, Slovak Republic) [113]. Nanothreading dismisses full multithreading for a nanothread that executes in the same register set as the main thread. The DanSoft nanothread requires only a 9 bit program counter, some simple control logic, and it resides in the same page as the main thread. The nanothread might be used to fill the instruction dispatch slots of a wide superscalar approach (like in simultaneous multithreading) without the need for several register sets.
But the main problem of todays superscalar microprocessor may not be found in the instruction window organization. It is the necessity of instruction completion/retirement due to the serial semantic of the instruction stream. For example, if a load instruction causes a secondary-level cache miss, the whole reorder buffer may soon be clogged by succeeding instructions (succeeding in sequential program order) that are already executed. Because of the sequential program order that should be restored by the completion stage, these instructions cannot be retired and removed from the reorder buffer even if the instructions are independent of the load instruction that caused the cache miss. The completion may be the main obstacle for further performance increase in microprocessors.
In principle, an algorithm defines a partial ordering of instructions due to control and true data dependences. The total ordering in an instruction stream for todays microprocessors stems from von Neumann languages. Why should
Historically, commercial parallel machines have demonstrated innovative organizational structures, often tied to a particular programming model, as architects sought to obtain the ultimate in performance out of any given technology. The period up to 1985 is dominated by advancements in bit-level parallelism (8-bit microprocessors was replaced by 16-bit, 32-bit etc.). Doubling the width of the datapath reduces the number of cycles required to perform an operation. The period from the mid-80s to mid-90s is dominated by advancements in the instruction-level parallelism, where the basic steps in instruction processing could be performed in a single cycle, most of the time. The RISC approach was straightforward to pipeline the stages of instruction processing so that an instruction is executed almost every cycle, on average. In order to utilize the parallelism in the hardware, it became necessary to issue multiple instructions in each cycle, called superscalar execution, as well as pipelining the processing of each instruction. Although superscalar execution will continue to be very important, barring some unforeseen breakthrough in instruction level parallelism, the leap to the thread-level parallelism is increasingly compelling as chips increase in capacity. Introducing thread-level parallelism on a single processor reduces the cost of the transition from one processor to multiple processors, thus making small scale SMPs more attractive on a broad scale. In additions, it establishes an architectural direction that may yield much grater latency tolerance in the long term. To conclude, there are strong indications that multithreading will be utilized in a future processor generations to hide the latency of local memory access [57].
Acknowledgements: The authors are grateful to referees of this paper for their meticulous review and many helpful comments.