We present deflection routing network on chip simulator (DNOC), a network-on-chip simulator. DNOC is primarily a deflection routing simulator, it simulates custom network topologies with detailed deflection router models, and a basic virtual channel router. DNOC can generate various statistics, such as network latency and power. We evaluate the simulator in three typical use cases. In stand-alone simulation, synthetic traffic generators are used to offer load to the network. In synchronous co-simulation, the simulator is integrated as a module within a larger system simulator with synchronization every simulated cycle. In the faster model-based co-simulation mode, a latency model is built, and retuned periodically at longer time intervals. We demonstrate co-simulation by running applications from the Rodinia and SPLASH-2 benchmark sets on mesh variants. DNOC is also able to run on multicore processors, speeding up the simulation of large networks.

We present DNOC, a network-on-chip simulator. DNOC simulates custom network topologies with detailed router models. Both classic virtual channel (VC) based router models and deflection routing models are supported. We validate the simulation models against hardware RTL router models. DNOC can generate various statistics, such as network latency and power. We evaluate the simulator in three typical use cases. In stand-alone simulation, synthetic traffic generators are used to offer load to the network. In synchronous co-simulation, the simulator is integrated as a module within a larger system simulator with synchronization every simulated cycle. In the faster model based co-simulation mode, a latency model is built, and re-tuned periodically at longer time intervals. We demonstrate co-simulation by running applications from the Rodinia and SPLASH-2 benchmark sets on mesh variants. DNOC is also able to run on multiple x86 cores in parallel, speeding up the simulation of large networks.

Digitalization has brought a tremendous momentum to health care research. Recognition of patterns in proteins is crucial for identifying possible functions of newly discovered proteins, as well as analysis of known proteins for previously undetermined activity. In this paper, the workload consists of locating patterns from the PROSITE database in protein sequences. We optimize the pattern search task by using a new breed of processors that merge network and server attributes. We leverage massive multithreading and regular-expression (RegX) hardware accelerators; the latter were designed and built for an entirely different application - high-bandwidth deep-packet inspection. Our multithreading optimization achieves 18x improvement, but by harnessing a RegX accelerator we were able to further demonstrate a significant 392x improvement relative to software pattern matching. Moreover, performance per area and power consumption are improved by multiple orders of magnitude as well.

We introduce a novel 3-D implementation of the interconnect between cores and shared L2 cache banks for multicore clusters. The 3-D structure extends cluster sizes that can be supported with tolerable wire delays. As a result of the shorter connections achieved by splitting existing 2-D design into four layers, performance is improved and area and power are reduced. The splitting enables implementation of a better arbitration scheme, which leads to additional performance improvement.

Recently, engineering solutions that include asymmetric multicores have been fabricated for low form-factor computing devices, indicating a potential direction for future evolution of processors. In this article we propose an asymmetric clustered core architecture, exhibiting low-latency switching between modes relative to asymmetric multicores, and having similarities with the same asymmetric multicore architecture in the context of a wider dynamic range of the processor power-performance characteristic. Asymmetric clustered cores incur additional microarchitectural complexity and area cost inside a core but exhibit better chip-level integration characteristics compared to asymmetric multicores. Focusing on power efficiency of asymmetric clustered cores, we describe: (1) a hierarchical power management partitioning between the operating system and on-die firmware for coarse-grain switch policies, and (2) core-internal tracking hardware for fine-grain switching. The mode switch policies of the core's tracking hardware are dependent on higher-level directives and hints from the operating system, on-die firmware, and compiler or profiling software. We further explore the potential power management benefits of asymmetric clustered cores relative to asymmetric multicores, demonstrating that the ability of asymmetric clustered cores to use tight training periods for adaptive behavior, with low overhead switching between modes, results in a more efficient utilization of power management directives.

Modern embedded processors used in media and communication portable devices are now required to execute complex applications and their performance requirements are getting close to the demands of general purpose processors. The performance-per-Watt ratio is an extremely important measure in portable devices because of their limited power capacity. Branch predictors, and especially the BTB, are among the largest on-chip SRAM structures (after caches), and therefore are primary contributors to the total system power. We propose a novel micro-architectural method referred to as Shifted-Index BTB with a Set-Buffer, which reduces both dynamic and static power. Extensive simulations show that up to 80% reduction in dynamic power is achieved at the cost of up to 0.64% system slowdown. 58% reduction is static power is also achieved by applying low-leakage power techniques that mesh well with the Set-Buffer design.

Multithreading is widely used to increase processor throughput. As the number of shared resources increase, managing them while guaranteeing predicted performance becomes a major problem. Attempts have been made in previous work to ease this via different fairness mechanisms. In this article, we present a new approach to control the resource allocation and sharing via a service level agreement (SLA)-based mechanism; that is, via an agreement in which multithreaded processors guarantee a minimal level of service to the running threads. We introduce a new metric, C SLA , for conformance to SLA in multithreaded processors and show that controlling resources using with SLA allows for higher gains than are achievable by previously suggested fairness techniques. It also permits improving one metric (e.g., power) while maintaining SLA in another (e.g., performance). We compare SLA enforcement to schemes based on other fairness metrics, which are mostly targeted at equalizing execution parameters. We show that using SLA rather than fairness based algorithms provides a range of acceptable execution points from which we can select the point that best fits our optimization target, such as maximizing the weighted speedup (sum of the speedups of the individual threads) or reducing power. We demonstrate the effectiveness of the new SLA approach using switch-on-event (coarse-grained) multithreading. Our weighted speedup improvement scheme successfully enforces SLA while improving the weighted speedup by an average of 10% for unbalanced threads. This result is significant when compared with performance losses that may be incurred by fairness enforcement methods. When optimizing for power reduction in unbalanced threads SLA enforcement reduces the power by an average of 15%. SLA may be complemented by other power reduction methods to achieve further power savings and maintain the same service level for the threads. We also demonstrate differentiated SLA, where weighted speedup is maximized while each thread may have a different throughput constraint.

Out-of-order speculative processors need a bookkeeping method to recover from incorrect speculation. In recent years, several microarchitectures that employ checkpoints have been proposed, either extending the reorder buffer or entirely replacing it. This work presents an in-dept-study of checkpointing in checkpoint-based microarchitectures, from the desired content of a checkpoint, via implementation trade-offs, and to checkpoint allocation and release policies. A major contribution of the article is a novel adaptive checkpoint allocation policy that outperforms known policies. The adaptive policy controls checkpoint allocation according to dynamic events, such as second-level cache misses and rollback history. It achieves 6.8% and 2.2% speedup for the integer and floating point benchmarks, respectively, and does not require a branch confidence estimator. The results show that the proposed adaptive policy achieves most of the potential of an oracle policy whose performance improvement is 9.8% and 3.9% for the integer and floating point benchmarks, respectively. We exploit known techniques for saving leakage power by adapting and applying them to checkpoint-based microarchitectures. The proposed applications combine to reduce the leakage power of the register file to about one half of its original value.

Misprediction is a major obstacle for increasing speculative out-of-order processors performance. Performance degradation depends on both the number of misprediction events and the recovery time associated with each one of them. In recent years a few checkpoint based microarchitectures have been proposed. In comparison with ROB-based processors, checkpoint processors are scalable and highly resource efficient. Unfortunately, in these proposals the misprediction recovery time is proportional to the instruction queue size. In this paper we analyze methods to reduce the misprediction recovery time. We propose a new register file management scheme and techniques to selectively flush the instruction queue and the load store queue, and to isolate deeply pipelined execution units. The result is a novel checkpoint processor with Constant misprediction RollBack time (CRB). We further present a streamlined, cost-efficient solution, which saves complexity at the price of slightly lower performance.

The need to reduce power and complexity will increase the interest in Switch On Event multithreading (coarse-grained multithreading). Switch On Event multithreading is a low-power and low-complexity mechanism to improve processor throughput by switching threads on execution stalls. Fairness may, however, become a problem in a multithreaded processor. Unless fairness is properly handled, some threads may starve while others consume all of the processor cycles. Heuristics that were devised in order to improve fairness in simultaneous multithreading are not applicable to Switch On Event multithreading. This paper defines the fairness metric using the ratio of the individual threads' speedups and shows how it can be enforced in Switch On Event multithreading. Fairness is controlled by forcing additional thread switch points. These switch points are determined dynamically by runtime estimation of the single threaded performance of each of the individual threads. We analyze the impact of the fairness enforcement mechanism on aggregate IPC and weighted speedup. We present simulation results of the performance of Switch On Event multithreading. Switch On Event multithreading achieves an average aggregate IPC increase of 26% over single thread and 12% weighted speedup when no fairness is enforced. In this case, a sixth of our runs resulted in poor fairness in which one thread ran extremely slowly (10 to 100 times slower than its single-thread performance), while the other thread's performance was hardly affected. By using the proposed mechanism, we can guarantee fairness at different levels of strictness and, in most cases, even improve the weighted speedup.

The need to reduce power and complexity will increase the interest in switch on event multithreading (coarse grained multithreading). Switch on event multithreading is a low power and low complexity mechanism to improve processor throughput by switching threads on execution stalls. Fairness may, however, become a problem in a multithreaded processor. Unless fairness is properly handled, some threads may starve while others consume all of the processor cycles. Heuristics that were devised in order to improve fairness in simultaneous multithreading are not applicable to switch on event multithreading. This paper defines the fairness metric using the ratio of the individual threads' speedups, and shows how it can be enforced in switch on event multithreading. Fairness is controlled by forcing additional thread switch points. These switch points are determined dynamically by runtime estimation of the single threaded performance of each of the individual threads. We analyze the impact of the fairness enforcement mechanism on throughput. We present simulation results of the performance of switch on event multithreading. Switch on event multithreading achieves an average speedup over single thread of 24% when no fairness is enforced. In this case, over a third of our runs achieved poor fairness in which one thread ran extremely slowly (10 to 100 times slower than its single thread performance) while the other thread's performance was hardly affected. By using the proposed mechanism we can guarantee fairness of 1/4, 1/2 and 1 for a small performance loss of 2.2%, 3.7% and 7.2% respectively

Summary form only given. The problem of compressed pattern matching deals with the ways to find a pattern within a compressed file, without decompressing. The techniques for solving the problem fall into two major categories, creating a unique compression scheme that enables efficient pattern matching; or using some known compression scheme and develop algorithms to search the files being produced. The first approach, which is the trade off compression for fast pattern matching, is selected. This proposed algorithm was also implemented and tested with some known files, such as Calgary and Canterbury corpora.

We introduce a new PLA-based decoder architecture for random-access runtime decompression of compressed instruction memory in embedded systems. The compression method employs class-based coding. The symbol codebook used for decompression is fully programmable; thus, good compression may be achieved by adapting the codebook to the symbol frequency statistics of the target binary program. We show that this new class-based decoder architecture can be extended to provide high throughput decompression.

Data compression and prediction are closely related. Thus prediction methods based on data compression algorithms have been suggested for the branch prediction problem. In this work we consider two universal compression algorithms: prediction by partial matching (PPM), and a recently developed method, context tree weighting (CTW). We describe the prediction algorithms induced by these methods. We also suggest adaptive algorithms variations of the basic methods that attempt to fit limited memory constraints and to match the non-stationary nature of the branch sequence. Furthermore, we show how to incorporate address information and to combine other relevant data. Finally, we present simulation results for selected programs from the SPECint95, SYSmark/32, SYSmark/NT, and transactional processing benchmarks. Our results are most promising in programs with difficult to predict branch behavior.

Accurate branch prediction is essential for providing higher performance levels in modern processors. Many branch predictors use branch execution history to identify repetitive branch behavior. Path history provides additional information that may help separate sequences of different branch instructions with identical execution history. We present a method to implement path history in hardware-based branch prediction, and a comprehensive simulation study of branch prediction strategies that integrate path history.

In todays microprocessors, when chip density increases and more execution units with deeper pipelines are integrated into the processor, accurate branch prediction is essential for providing higher performance levels.Many recent branch predictors use branch execution history to identify repetitive branch behavior.By recording address information of recently executed branches, we can separate sequences of different branch instructions with identical execution history.The use of path history information has been recently addressed by Young and Smith [l] in static branch correlation, and by Young et el.[2] and Nair [3] in dynamic branch prediction methods.We present a method to implement path history in hardware-based branch prediction, and a comprehensive simulation study of branch prediction strategies integrating path history.Pmksion lo m&c digital/hard copicq of all or pnri ofthis n,aterinl for P~on~l or cl-m use is granted without fee provided fiat he copies we not nude or distributed for profir or ~ununercinl advantage.he copyright nuti% tie title ofthe publication and its date appear, ,md notice is given Ihat copyright is by pernksion ofthe ACM, Inc.To copy othe&se.lo republish.lo post on servetx or to redistribute to Ii.*, require specific petmission iu&or fee

A dependence for data, control, or resources might cause one instruction to become stalled in a pipeline stage waiting for a preceding instruction to produce a result or release a resource. The pipeline control hardware checks for dependences, and prevents the instruction from going to the next pipeline stage if a dependence occurs. We refer to this hardware as interlock logic. The amount and complexity of the interlock logic required to support a ten+ instruction issue bandwidth is a major concern in the design of the pipeline control hardware. We look specifically at register interlocks in the context of a parallel pipeline with separate dispatch and issue phases-a generalization of the pipeline organization implemented by a number of prominent recent superscalar processors. We describe four implementations of the register interlock logic and a comparison based on the number of logic levels. We also present a high-bandwidth implementation of table-based register renaming.>

Interleaved memories are essential in pipelined computers to attain high memory bandwidth. As a memory bank is accessed, a reservation is placed on the bank for the duration of the memory cycle, which is often considerably longer than the processor cycle time. This additional parameter, namely, the bank reservation time or the bank busy time, adds to the complexity of the memory model. For Markov models, exact solutions are not feasible even without this additional parameter due to the very large state space of the Markov chain. The authors develop a Markov model which explicitly tracks the bank reservation time. Because only one processor and the requested bank are modeled, the transition probabilities are not known and have to be approximated. The performance predicted by the model is in close agreement with simulation results.>

This paper studies two compilation techniques for enhancing scalar performance in high-speed scientific processors: software pipelining and loop unrolling. We study the impact of the architecture (size of the register file) and of the hardware (size of instruction buffer) on the efficiency of loop unrolling. We also develop a methodology for classifying software pipelining techniques. For loop unrolling, a straightforward scheduling algorithm is shown to produce near-optimal results when not inhibited by recurrences or memory hazards. Our study indicates that the performance produced with a modified CRAY-1S scalar architecture and a code scheduler utilizing loop unrolling is comparable to the performance achieved by the CRAY-1S with a vector unit and the CFT vectorizing compiler. Finally, we show that the combination of loop unrolling and dynamic software pipelining, as implemented by a decoupled computer, substantially outperforms the vector CRAY-1S.

One of the most noticeable differences between the CRAY-2 and its predecessors, the CRAY-1 and the CRAY X-MP, is a significantly longer memory path. This is a consequence of increasing the size of the memory at the expense of the bank access time. With a longer memory path, the impact of bank conflicts becomes more apparent. In this paper we study a storage strategy for vector processors that has the following properties: (1) it is aperiodic, (2) it tends to distribute references more uniformly over the memory banks, (3) the implementation of the addressing hardware is straightforward, and (4) the delay added to the memory path is minimal. The first two properties help in reducing the frequency of bank conflicts.

High-performance scalar architectures that have the capability to issue multiple instructions per clock period are considered. The essential characteristics and the principal architectural tradeoffs in scientific array processors, very-long-instruction-word (VLIW) machines, the polycyclic architecture and decoupled computers are examined. Array processors rely solely on static code scheduling done manually or by the compiler. The scheduling task is quite complex, and the resulting code may not be very efficient. In a VLIW, sophisticated compiler technology provides software solutions for functions traditionally done in hardware. The polycyclic architecture is similar to array processors in its structure but provides architectural support to the instruction scheduling task. In decoupled architectures the hardware changes the order of instruction execution at run time. This dynamic code scheduling capability does not come at the expense of additional control complexity.>

This paper studies two compilation techniques for enhancing scalar performance in high-speed scientific processors: software pipelining and loop unrolling. We study the impact of the architecture (size of the register file) and of the hardware (size of instruction buffer) on the efficiency of loop unrolling. We also develop a methodology for classifying software pipelining techniques. For loop unrolling, a straightforward scheduling algorithm is shown to produce near-optimal results when not inhibited by recurrences or memory hazards. Software pipelining requires less hardware but also achieves less speedup. Finally, we show that the performance produced with a modified CRAY-1S scalar architecture and a code scheduler utilizing loop unrolling is comparable to the performance achieved by the CRAY-1S with a vector unit and the CFT vectorizing compiler.

Decoupled architectures achieve high scalar performance by cleanly splitting instruction processing into memory access and execution tasks. Several decoupled architectures have been proposed, and they all have two characteristics in common: 1) they have two separate sets of instructions, one for accessing memory and one for performing function execution. 2) The memory accessing task and the execution task communicate via architectural queues.

Abs~t

Basic principles and design tradeoffs for control of pipelined processors are first discussed. We concentrate on register-register architectures like the CRAY-1 where pipeline control logic is localized to one or two pipeline stages and is referred to as "instruction issue logic." Design tradeoffs are explored by giving designs for a variety of instruction issue methods that represent a range of complexity and sophistication. These vary from the CRAY-1 issue logic to a version of Tomasulo's algorithm, first used in the IBM 360/91 floating point unit. Also studied are Thornton's "scoreboard" algorithm used on the CDC 6600 and an algorithm we have devised. To provide a standard for comparison, all the issue methods are used to implement the CRAY-1 scalar architecture. Then, using a simulation model and the Lawrence Livermore Loops compiled with the CRAY Fortran compiler, performance results for the various issue methods are given and discussed.