The Use of Multithreaded Processors in DASH

The Use of Multithreaded Processors in DASHSugath Warnakulasuriyaemail: sugath@AbstractDASH is a scalable shared memory multiprocessor architecture which employs directory based cache coherence. Due to the physical distribution of the memory in DASH, there is potential for long memory latency. Although a number of latency reducing and hiding techniques such cach-ing, a weaker memory consistency model, and pre-fetching are employed by DASH, the use of Multithreaded processors is not currently included in the design. In this paper, the use of Mul-tithreaded processors in the DASH architecture is examined. A processor architecture which in-corporates multithreading with superscalar capabilities is proposed, and a general discussion of issues regarding multithreading as well as the incorporation of the proposed multithreaded processor into the existing DASH architecture is presented.1 - IntroductionDASH is a scalable shared memory multiprocessor architecture which employs directory based cache coherence. The memory is physically distributed among a potentially large number of processing nodes, leading to a NUMA (Non-Uniform Memory Access) model with relatively long latency for access to remote memory. Although the DASH provides local caches and en-courages the exploitation of data locality to minimize the need for remote memory access, the average memory access time is still significantly impacted by long latencies associated with re-mote memory access. Although the DASH supports a number of latency reducing and hiding techniques (including a weaker memory consistency model, caching, and pre-fetching), the use of Multithreaded processors is not currently included in the design. In this paper, we explore the issues relating to the use of Multithreaded processors in the DASH architecture.An overview of the DASH architecture and its features are presented in Section 2. A general discussion of issues in multithreading is presented in Section 3. An architectural framework for a multithreaded superscalar processor is proposed in Section 4, followed by a brief discus-sion of the issues involved in incorporating the proposed processor into the existing DASH ar-chitecture (in Section 5).2 - Overview of the DASH ArchitectureDASH is a MIMD shared memory multiprocessor architecture intended to be used for a broad range of applications. The architecture preserves the advantages in programmability of a sin-gle address space while maintaining scalability, an attribute traditionally associated with dis-tribu ted memory systems ("Mu lticompu ters"). The DASH mu ltiprocessor was designed to providing scalable memory bandwidth with limited overhead and cost, while reducing or hid-ing latency associated with large memory systems.DASH presents a single address space which encompasses all distributed shared memory. By doing so, it provides a simpler programming model than that provided in distributed memory system (where a programmer must structure the data to account for the distributed memory architecture, and must explicitly support the communication of shared data). A single address space also provides for easier program/data partitioning and dynamic load distribution, where-as in a message passing system, tasks and data must be explicitly migrated.The DASH architecture supports a general, scalable network topology. Each node in the net-work is a "Cluster", with each cluster itself being a small scale bus-based multiprocessors. In the proposed DASH configuration, each cluster is made of 4 processors. Processors in a cluster share a single memory module, with the memory modules of all clusters making up the global memory. All processors in a cluster share a single directory and network interface logic, allow-ing the high cost of these specialized components to be amortized over multiple processors. Fig-ure 1 presents a high-level view of the DASH architecture.Figure 1 - Overview of DASH ArchitectureA 64 processor prototype of the DASH has been built to demonstrate the feasibility of and to identify the limitations of the DASH architecture. This prototype consists of 16 clusters, with each cluster containing 4 processors. The estimated peak performance of this 64-processor sys-tem is 1.6 GIPS (and 600 MFLOPS). The prototype has been implemented u sing Silicon Graphics 4D/340 processors and customized directory and controller hardware. The imple-mented prototype is based on a pair of wormhole-routed mesh networks (to support indepen-dent request and reply networks).Traditionally, mu ltiprocessor cache coherence is achieved u sing snoopy protocols. In these schemes, each processing node monitors all requests to memory and independently determines the state of its cache. Such multiprocessors are usually bus based, and employ broadcast mes-sages to distribute state updates to memory (broadcast of invalidations and/or update messag-es). However, such bus-based schemes are not scalable since the fixed bus bandwidth is shared by all processors. Also, broadcasting memory requests to every cache may saturate the system, thereby making these schemes inappropriate for large scale multiprocessors. Note however that a snoopy protocol is used for intra-cluster cache coherence in DASH.To overcome these limitations, DASH supports general network interconnects and uses direc-tories for cache coherence. Cache coherence is maintained using dedicated hardware (as op-posed to software) in order to achieve better performance. This removes the burden of cache coherence from software. Cache coherence in DASH is maintained using point-to-point mes-sages instead of broadcast messages.Directories in DASH are partitioned and distributed, thereby eliminating the bottleneck prob-lems associated with centralized directory schemes. This too contributes to the scalability of DASH. DASH directories use bit vectors of "presence bits" to maintain coherence. Although the hardware and memory overhead for directory based coherence is a potential problem for machines with a large number of processors, many schemes which limit this overhead to a small fraction of total system cost have been proposed (limited pointer directories, etc.). These schemes are beyond the scope of this paper, and will not be discussed further.The DASH protocol is based on the use of point-to-point messages. The protocol uses message forwarding to achieve a highly efficient, non-blocking scheme. The protocol supports the auto-matic serialization of remote memory requests (serialization performed by the cluster which currently owns a particular block). Also, acknowledgments are used to detect "global comple-tion" of memory operations. Memory requests originating from processors in the same cluster are merged, thereby making the intra-clusters cache coherence activities transparent to the outside.By physically distributing memory throughout the system, the DASH presents a NUMA (Non-Uniform Memory Access) model. Although all memory is globally accessible, some memory is more costly than other to access. Conceptually, DASH presents a memory access hierarchy of 5 levels, with each lower level being more costly to access (the levels and their associated la-tencies are presented in Figure 2). This hierarchy allows exploiting the principle of locality by maintaining data "closer" to where it is actually used, thereby reducing the average latency of memory accesses and reducing bandwidth requirements of the global interconnect.Figure 2 - DASH Memory Access LevelsThe "memory access hierarchy" in DASH consists of the following levels:• Processor Level - desired data found in local processor cache (requires 1 processor clock for access)• Local Cluster Level - desired data found in other processor cache within the local cluster (re-quires 30 processor clocks for access)• Directory Home Level - an up-to-date copy of the desired data found at its "home" using the directory and main memory associated with given address - (requires 100 processor clocks for access)• Remote Cluster Level - desired data found in a processor cache of a remote cluster - (requires 135 processor clocks for access)DASH employs both memory latency reducing (decreasing the time required to access memory) and latency hiding (overlapping memory latency with additional compu tation) techniqu es. The primary latency reducing technique is the use of local caches, which are especially effective for applications which display a great degree of locality. Also, the multi-level memory access hierarchy in DASH allows further reduction in latency by pre-fetching data whose use can be anticipated, and therefore, brought closer.The nature of the DASH cache coherency protocol also leads to a reduction in latency. This is due to the minimization of the number of nodes that must be accessed to satisfy a memory re-quest, and use of a non-blocking message forwarding scheme.The latency hiding techniques employed by DASH include the support of data pre-fetching and the use of a weak memory consistency model. The pre-fetch operation supported is a non-bind-ing, software controlled operation, intended to be explicitly issued by a processor. The pre-fetch allows compilers/applications to aggressively pre-fetch values when data usage can be an-ticipated.DASH also uses release consistency, which helps hide latency to write operations (however, it does not help hide latency of read misses). To support release consistency, a write buffer is used to hold all writes issues by a processor. Also, "Fence" operations (which are explicit stall commands to the write buffer and or processor) are supported in DASH. This allows the com-piler/programmer to emulate any memory consistency model.A latency reducing technique not employed by DASH is the use of multithreaded processors. Mu ltithreading is the overlapping of commu nication (to access remote memory) and u sefu l computation by utilizing an otherwise idle processor to execute another task while a long la-tency memory operation is being made. Note that this concept is analogous to context switch-ing caused by page-faults in virtual memory systems. The need to build a working prototype along with the lack of commercially available multithreaded processors has led to the omission of this promising latency hiding technique from DASH. The reminder of this paper will discuss multithreading and its incorporation into DASH.There are a number of other interesting features in the DASH architecture. A description of these as well as a more detailed description of the overall architecture and the coherence pro-tocol can be found in [6] and [7].3 - Issues in MultithreadingThe following subsections present a discussion of the following:• Issues which have motivated the use of multithreaded processors• The various choices involved in the design of multithreaded processors•The tradeoffs associated with the use of multithreaded processorsThis discussion is intended to lay the ground work for the justification of the multithreaded processor proposed in Section 4.3.1 - Latency hiding through increased resource utilizationEven with the use of caches and other methods such as pre-fetching to exploit locality in appli-cations, it is unrealistic to expect that all references to remote memory can be eliminated. This has been su fficiently demonstrated in attempts to solve analogou s problems su ch as cache block and virtual memory page placement/replacement techniques. Furthermore, in multipro-cessor applications, there is a great likelihood of processes residing on independent processors needing to work together to solve a single problem, hence requiring inter-process communica-tion (IPC) and/or synchronization using shared variables. This demands that remote memory latency be further reduced or eliminated in order to maximize program performance.For example, based on the DASH memory latency presented in Figure 2, and assuming conser-vative "hit-ratios" of 85% for the Processor Level, 8% for the Local Cluster Level, 5% for the Directory Home Level, and 2% for the Remote Cluster Level, an average memory latency of 10.95 cycles is obtained. This can be a large performance penalty to pay, especially for memo-ry-intensive programs. During the execution of such applications, the processor will be idle for a substantial percentage of the time (during which the remote memory is accessed). This un-der-utilization of the processor in single-threaded systems is illustrated in Figure 3a.Figure 3a - Under-utilization of a single-threaded processorAssuming that all other means (both static and dynamic) of reducing and hiding latency have been attempted, methods to utilize the idle processor resources must now be explored. From this arises the motivation for multithreading: the utilization of the idle processor cycles during the memory operation of one thread to execute instructions of other threads. A simple example of increased processor utilization through multithreading is illustrated in Figure 3b.Figure 3b - Increased processor utilization due to Multithreading3.2 - Context Switching PoliciesAssuming that multithreading is to be used for hiding memory latency, a context switching policy must be established (such a policy dictates the conditions under which the processor switches from executing one thread to another). Although a number of context switch policies are described by Hwang in [4], only the following two policies are considered as candidates for the multithreaded processor proposed in the next section:• Switch on cache miss: this policy calls for a thread to relinquish the processor when a cache miss (or a similar long latency operation) is encountered. Note that this policy is generally re-ferred to as a "Blocked" scheme [5]. The April multithreaded processor used in the Alewife sys-tem utilizes this type of policy [2].• Switch on every cycle: this policy calls for a thread to relinquish the processor after each cy-cle, regardless of the type of instruction encountered. Instructions of multiple threads are in-terleaved, and "serviced" in a round-robin fashion. Note that this policy is generally referred to as an "Interleaved" scheme [5]. The HEP [12] and Tera [4] architectures utilize this type of policy.According to studies by Laudon, et. al., cycle-by-cycle switching can yield better performance than comparable "blocked" schemes [5]. It has been concluded that the complexity of imple-menting cycle-by-cycle context switching is not overwhelmingly, and that as pipelines get deep-er (and operate at a lower percentage of peak performance), the performance advantages of the cycle-by-cycle switching can justify additional complexity. In [5], it is also shown that the rel-ative advantage of the interleaved scheme is greater for deeper pipelines, and that the perfor-mance increases along with an increased number of threads. A more precise model of this behavior, along with a discussion of "linear" and "saturated regions" is presented in [4].3.3. - Additional Benefits of MultithreadingIn addition to helping hide latency, multithreading can also help remove pipeline dependen-cies. Generally, it can be assumed that instructions in different threads are independent. So, in a cycle-by-cycle context switching scheme employing pipelined units, pipeline stalls due to dependencies are all but eliminated assuming the number of concurrent threads match the number of pipeline stages. A simple example of this, assuming four pipeline stages, and four threads is illustrated in Figure 4. Note that instructions I1 and I2 of thread T1are dependent, and cannot be executed in successive pipeline steps in a single-threaded architecture. How-ever, due to the interleaving the of the instructions from the four independent threads, the de-pendency between the instructions I1 and I2 of Thread T1 has disappeared when I2 enters the pipeline.Figure 4 - Elimination of pipeline stalls due to multithreadingAn example of an actual implementation of such a scheme is the HEP processor, which, given 8 active threads, issues one instruction from each thread every 8 cycles. Since there are 8 pipe-line stages in the HEP processors, the previous instruction of a thread completes execution pri-or to the issuance of a new instruction from the same thread, thereby eliminating pipeline stalls due to dependencies. This type of scheme reduces and/or eliminates the need for special-ized hardware and/or compiler resources required to resolve pipeline hazards.Another important aspect of multithreading is that both hiding memory latency and reducing/ eliminating pipeline stalls can be achieved with no impact to application software. Multi-threading is completely transparent to the programmer, and comes at no additional program-ming cost.3.4 - Context Switching CostsGenerally, the cost of context switching should be small enough so as to not outweigh the ben-efits of multithreading. Intuitively, it can be assumed that more efficient and more complex context switching mechanisms are required to support the more aggressive context switching policies in order to maintain the benefits of multithreading. For example, the Tera architec-ture [4] (which calls for aggressive cycle-by-cycle context switching) provides highly efficient hardware context switching using 128 separate sets of registers (and other hardware) to main-tain the states of the individual threads. An earlier architecture, the HEP [12], uses a slightly different scheme, in which a set of 1024 general purpose registers (referred to as "Register Memory") is shared by all threads in the system. Hardware is used to maintain the set of reg-isters in the register memory which belongs to a particular thread (using base and limit regis-ters) in order to protect the state of a thread.Although complex hardware is required for instruction issue and thread management in a cy-cle-by-cycle context switching scheme, the runtime context switch cost for this should be zero. In other words, the fact that successive instructions entering a pipeline may belong to multiple threads should be transparent to the pipeline, and it should have no impact to the delay in propagating instructions from one pipeline stage to another.On the other hand, less aggressive context switching policies (i.e., switch on cache miss) do not require as efficient mechanisms to maintain the benefits of multithreading (due to their rela-tive infrequency of use). Less aggressive policies can be supported with a less complex set of hardware (and perhaps even aided with software). Such an implementation (the April multi-threaded processor), which uses existing register windows in the Sparc processor with slight enhancements, is presented in [2]. According to Laudon [5], the cost of a context switch for this type of switching policy corresponds to the number of instructions from a context to be swapped out that have already entered the pipeline (as these instructions must be removed from the pipeline).Performance models for determining the efficiency of multithreaded processors which take into account the cost and the frequency of context switching are presented in [2] and [4].3.5 - Drawbacks and Limitations of MultithreadingAlthough multithreading leads to the better utilization of processor resources, helps hide mem-ory latency, and may help hide dependencies, it poses several potential problems which must be resolved in order for it to be used.3.5.1 - Cache ConflictsEach thread has associated with it a "working set" of data. For optimal performance, this working should reside in the processor cache when the thread executes (so that a maximum amount of memory references lead to "cache hits"). In most applications, the working sets of independent threads are disjoint, leading to one or more of the following problems:• Placing all of the working sets of all threads in the cache simultaneously may be impractical given that an extremely large cache is likely to significantly decrease the cost-performance of a system. This is compounded by the fact that individual working sets may themselves be quite large. However, given the decreasing costs in hardware, a sufficiently large cache may be a viable solution.• With a limited cache size, thrashing (leading to unacceptable memory traffic conditions) may occur as context is switched from one thread to another, requiring working sets of threads to be swapped in and out of the cache. Such conditions are more likely when cycle-by-cycle con-text switching is performed.Potential solutions to reducing the likelihood of thrashing conditions are discussed in the next section.3.5.2 - Lack of Inherent Parallelism in ApplicationsIn order for multithreaded processors to be effective, it is necessary to partition applications/ problems into medium to small grain threads (i.e., achieve task level parallelism). This is es-pecially true in systems which rely on cycle-by-cycle context switching and deep pipelines to hide memory latencies. For example, the Tera architecture (described [4]) require 128 concur-rent threads in order to achieve optimal performance.Given that such processors are a part of a large multiprocessor system, and that each such pro-cessor requires a set of 128 threads for optimal performance (to keep the pipeline full), it is dif-ficult to imagine how a single application could be partitioned into such a large number of parallelizable threads given the current software technology for identifying parallelism. How-ever, it should be kept in mind that some of the threads could be in support of the operating system, and not all such threads need to be from a common application.Also it should be noted that an extensive set of advanced software tools are needed to fully uti-lize such a system. For example, new languages which allow more natural expression of inher-ent parallelism in problems as well as more advanced parallelizing compilers are required. 3.5.3 - Performance of Single ThreadsAlthough the interleaving of multiple threads leads to better processor resource utilization and throughput, the performance of a single may degrade as a result of multithreading.For example, in cycle-by-cycle context switching policies, threads are "swapped out" regardless of the type of instruction encountered (i.e. whether a cache miss occurs or not). Furthermore, the thread is "serviced" once again only after a single instruction of each of the other active threads is serviced. This tends to severely penalize threads with high cache hit ratios (that require little or no remote memory access), especially in the presence of a large number of other threads. More precisely, the maximum performance possible under cycle-by-cycle context switching is one instruction for every n cycles where n equals the depth of the pipeline. So run-ning a single thread at optimal performance is not possible.Ideally, a multithreaded processor should also support the execution of successive instructions from a single thread, assuming there are no dependencies between the instructions, and that the instructions do not cause long latency operations. Such a multithreaded processor would then be able to not only hide latency and eliminate pipeline stalls when appropriate, but also satisfy applications requiring near peak performance to be served as in a single-threaded pro-cessor. This has been taken into consideration in the design of the proposed multithreaded ar-chitecture proposed in the next section.3.6 - Multithreading support for superscalar processorsSo far, multithreading has been discussed with little reference to some of the latest advance-ments in modern processor architectures. The most important among these is the concept of superscalar architectures, which employ multiple functional units (possibly the use multiple units of a particular type), and are capable of issuing multiple instructions in a single clock cycle.Recent experience with the use of superscalar processors has revealed the following:• Instruction level parallelism available in a single instruction stream is limited• Functional units in superscalar architectures are often under-utilized due to the lack of in-struction level parallelism in single instruction streamsIn exploring multithreading, the most aggressive context switch strategy considered so far has been cycle-by-cycle context switching. Given the availability of multiple functional units in su-perscalar architectures, and the desire to maximize the utilization of these functional units, the issuing of multiple instructions (from potentially independent threads) during a single clock cycle should be considered. By doing so, the concept of a "context switch" is blurred.A simple example of the use of a multithreaded superscalar processor is illustrated in Figure5. Note that the utilization of functional units is maximized due to the availability of instruc-tions from multiple threads.Figure 5 - Instruction Issue using multithreaded superscalar processorThe concept of incorporating multithreading into a superscalar architecture forms the basis for the multithreaded processor proposed in the following section.4 - Proposed Design of a Multithreaded Superscalar ArchitectureBased on the discussions in the previous section, a high-level design of a new multithreaded superscalar architecture is presented below. A high-level diagram of this architecture is pre-sented in Figure 6.Figure 6 - Multithreaded superscalar architectureThe following are the main components of the proposed multithreaded superscalar processor:•Instruction Cache: maintains instructions belonging to multiple threads read in from the main memory. Instructions for different threads are fetched from main memory under the guidance of the Thread Management Unit. Data cache size should be determined based on the maximum number concurrent threads to be supported by the system, and the overall issue rate of the processor.• Thread management Unit (TMU): examines the dependence of the instructions within each thread, and schedules the execution of eligible instructions (based on dependency analysis). The instructions are scheduled by placing them in available slots in the instruction buffer. This components also manages the states of the individual threads.• Instruction Buffer: manages very long instruction words (VLIWs). Each instruction word contains multiple instructions, each of which may belong to a different thread.•Instruction Issue Logic: issues instructions from the instruction buffer based on the avail-ability of functional units. This component may issue instructions belonging to multiple threads during a single clock cycle.• Functional Units: a number of specialized functional units (integer units, floating point units, branch units, etc.). The type and number of units is to be determined based on analysis of the utilization of resources by multiple concurrent threads.• Register File: maintains a register set for each active threads in the system. The actual num-ber of register sets required should be scalable, and should be determined based on the maxi-mum number concurrent threads to be supported by the system.•Data Cache: maintains working sets of data belonging to the active threads. Since a large number of threads may be active, a sufficiently large cache must be provided to simultaneously hold multiple working sets.Although this is a simplified, very high level design (or framework) for a multithreaded super-scalar processor, it illustrates the components necessary for such an architecture.。