The resource sharing nature of Simultaneous Multithreading (SMT) processors and the presence of long latency instructions from concurrent threads make the instruction scheduling window (IW), which is a primary shared component among key pipeline structures in SMT, a performance bottleneck. Due to the tight constraints on its physical size, the IW faces more severe pressure to handle the instructions from various threads while attempting to avoid resource monopolization by some low-ILP threads. It is particularly challenging to optimize the efficiency and fairness in IW utilization to fulfill the affordable performance by SMT under the shadow of long latency instructions. Most of the existing optimization schemes in SMT processors rely on the fetch policy to control the instructions that are allowed to enter the pipeline, while little effort is put to control the long latency instructions that are already located in the IW. In this paper, we propose streamline buffers to handle the long latency instructions that have already entered the pipeline and clog the IW, while the controlling fetch policies take time to react. Each streamline buffer extracts from IW and holds a chain of instructions from a thread that are stalled by dependency on a long latency load. When the load value returns, the streamline buffer then serves these instructions directly to in-order execution, avoiding any instruction replay. This is done in supplement to the conventional IW that serves in parallel the other instructions for out-of-order (o-o-o) execution. Analysis of SPEC2000 integer and FP benchmarks reveals that instructions dependent on long latency loads, typically have their first source operand ready within 5 percent-15 percent of their total wait time in the IW. Our scheme is able to utilize this asymmetry in source operands' ready time to achieve a complexity effective design. As compared to the baseline SMT architecture, our design when working in conjunction with earlier proposed ICOUNT.2.8 fetch policy for 4-threads effectively reduces the IW full rate by 9.4 percent (11 percent for 2-thread), improves average IPC for MIXED workloads by 9.6 percent (8 percent for MEM workloads and 4.4 percent for CPU workloads), and fairness by 7.56 percent (7.24 percent for 2-thread). Similar enhancements are observed when run in conjunction with an RR.2.8 fetch policy. Further, our scheme when combined with DCRA improves the performance on the average by 21.7 percent, while DCRA improves by 16.3 percent when run alone.

The increase in the complexity of a wide-issue processor with its pipeline width is one of the primary concerns of processor designers. In the conventional design, the hardware in the processor core is laid out to handle multiple instructions with two source operands in each pipeline stage. However, an analysis of SPEC2000 programs reveals that an integer program on the average constitutes 25.2 percent of two-op (both source registers) integer instructions and 72.5 percent of one-op/zero-op integer instructions. Floating-point (FP) programs are found to constitute on the average 15.8 percent of two-op integer instructions and 44.1 percent of one-op/zero-op integer instructions. The analysis observes that the hardware laid out for worst-case requirements in the integer pipeline is highly underutilized for a significant portion of time. To alleviate the complexity issues, we propose the split pipeline architecture, a novel technique to distinguish and process instructions based on their source operand requirements. The conventional pipeline is split into two after the decode stage, and the two pipelines are again converged at the execution stage. This leads to a capability of processing instructions at a higher clock rate and at almost the same instruction-per-cycle (IPC) throughput, as compared to a conventional processor. Various flavors of the proposed architecture are simulated and analyzed in this paper, with a circuit level analysis to determine the impact on the critical path delays. Results show that a processor that can fetch, decode, and commit eight instructions in each cycle and with split pipelines of two two-source integer instruction and six zero/one-source integer instruction can achieve a clock rate that is 15.8 percent faster than an eight-wide conventional processor while reducing the IPC throughput by only 0.7 percent for SPEC2000 benchmarks. Similarly, a four-wide processor with split pipelines of one two-source integer instruction and three zero/one-source integer instructions can achieve a clock rate that is 19.69 percent faster than a four-wide conventional processor while reducing the IPC throughput by only 1.9 percent.

The increase in the circuit complexity of a wide-issue processor with its pipeline width is one of the primary concerns of the processor designers. In the conventional design, hardware in the processor core is laid out to handle multiple instructions with two-source operands in each pipeline stage. However, analysis of characteristics of the SPEC2000 integer programs reveals that 74% of instructions require one or less source register operands, and FP programs on average have 60% integer instructions three-fourth of which require one or less source register operands. To alleviate the complexity issues we propose split pipeline architecture, a novel technique to distinguish and process integer instructions based on their source operand requirements. This leads to a capability of processing instructions at a higher clock rate and at almost the same IPC, as compared to a conventional processor.

Current day wide-issue processors require the fetch engine in the frontend to continuously supply instructions to the issue queue in the backend to extract maximum possible amount of instruction level parallelism (ILP). Further, due to the continuous access of level-1 instruction cache (IL1) for fetching instructions, the power dissipation due to switching activity in IL1 is overwhelmingly high and continuous, and hence IL1 is one of the prominent hot-spots on the chip. In this paper, we alleviate the effect of control dependencies whenever a branch instruction forms a small loop. We use replicator architecture, a novel mechanism to supply twice the number of loop instructions in the same cycle, leading to a faster supply of instructions to the backend. This leads to an improvement in processor throughput in terms of instructions committed per cycle (IPC) due to extraction of higher ILP. Further, the mechanism results in a significant reduction in the total number of IL1 accesses. Implementation of the proposed technique in an 8-wide out-of-order issue processor results in a 19% improvement in IPC, and a 8.5% reduction in overall energy consumption on average, for various processor evaluation benchmark programs. Further, an enhanced Replicator mechanism results in larger reduction in IL1 accesses, leading to a 16% reduction in the overall energy consumed. The enhanced architecture removes the continuity in the access to the IL1 by feeding the instructions to the backend all by itself whenever a loop occurs. This gives a break to switching activity in IL1 and hence mitigates the hot-spot problem in the frontend of the processor.

With the advent of clustered microarchitectures, the rename map table at the front-end is shared by the clusters, and hence it's critical path delay should not become a bottleneck in determining the processor clock cycle time. Also, renaming logic in the front-end is one of the largest contributors of peak temperatures on the chip, and so demands attention to reduce the power consumption. Analysis of characteristics of Spec2000int programs reveals that, when the programs are processed in a 4-wide (8-wide) processor, none or only one two-source instruction (an instruction with two source registers) is renamed in a cycle for 94% (92%) of total execution time. In this paper, we propose a novel technique to significantly reduce the number of ports in the rename map table. The novelty of the technique is that it is easy to implement and succeeds in reducing the access time, power, and area of the rename logic, without any additional power, area, and delay overheads in any other logic on the chip. With this technique in an 8-wide processor, a rename map table with 9 read ports, instead of 16, results in a reduction in access time, power, and area by 14%, 42%, and 49%, respectively, with only 4.7% loss in IPC. Similar gains are also seen in a 4-wide processor

In modern day high-performance processors, the complexity of the register rename logic grows along with the pipeline width and leads to larger renaming time delay and higher power consumption. Renaming logic in the front-end of the processor is one of the largest contributors of peak temperatures on the chip and, so, demands attention to reduce the power consumption. Further, with the advent of clustered microarchitectures, the rename map table at the front-end is shared by the clusters and, hence, its critical path delay should not become a bottleneck in determining the processor clock cycle time. Analysis of characteristics of Spec2000 integer benchmark programs reveals that, when the programs are processed in a 4-wide processor, none or only one two-source instruction (an instruction with two source registers) is renamed in a cycle for 94 percent of the total execution time. Similarly, in an 8-wide processor, none or only one two-source instruction is renamed in a cycle for 92 percent of the total execution time. Thus, the analysis observes that the rename map table port bandwidth is highly underutilized for a significant portion of time. Based on the analysis, in this paper, we propose a novel technique to significantly reduce the number of ports in the rename map table. The novelty of the technique is that it is easy to implement and succeeds in reducing the access time, power, and area of the rename logic, without any additional power, area, and delay overheads in any other logic on the chip. The proposed technique performs the register renaming of instructions in the order of their fetch, with no significant impact on the processor's performance. With this technique in an 8-wide processor, as compared to a conventional rename map table in an integer pipeline with 16 ports to look up source operands, a rename map table with nine ports results in a reduction in access time, power, and area by 14 percent, 42 percent, and 49 percent, respectively, with only 4.7 percent loss in instructions committed per cycle (IPC). The implementation of the technique in a 4-wide processor results in a reduction in access time, power, and area by 7 percent, 38 percent, and 59 percent, respectively, with an IPC loss of only 4.4 percent.

One of the central issues in router performance is IP address lookup based on longest prefix matching. IP address lookup algorithms can be evaluated on a number of metrics-lookup time, update time, memory usage, and to a less important extent, the time to construct the data structure used to support lookups and updates. Many of the existing methods are geared toward optimizing a specific metric, and do not scale well with the ever expanding routing tables and the forthcoming IPv6 where the IP addresses are 128 bits long. In contrast, our effort is directed at simultaneously optimizing multiple metrics and provide solutions that scale to IPv6, with its longer addresses and much larger routing tables. In this paper, we present two IP address lookup schemes-Elevator-Stairs algorithm and logW-Elevators algorithm. For a routing table with N prefixes, The Elevator-Stairs algorithm uses optimal O(N) memory, and achieves better lookup and update times than other methods with similar memory requirements. The logW-Elevators algorithm gives O(logW) lookup time, where W is the length of an IP address, while improving upon update time and memory usage. Experimental results using the MAE-West router with 29 487 prefixes show that the Elevator-Stairs algorithm gives an average throughput of 15.7 Million lookups per second (Mlps) using 459KB of memory, and the logW-Elevators algorithm gives an average throughput of 21.41Mlps with a memory usage of 1259KB.

Large register file with multiple ports, but with a minimal access time, is a critical component in a superscalar processor. Analysis of the lifetime of a logical to physical register mapping reveals that there are long latencies between the times a physical register is allocated, consumed, and released. In this paper, we propose a TriBank register file, a novel register file organization that exploits such long latencies, resulting in a larger register bandwidth and a smaller register access time. Implementation of the TriBank register file organization, as compared to a conventional monolithic register file in an 8-wide out-of-order issue superscalar processor reduced the register access time up to 34%, even while enhancing the throughput in instructions per cycle (IPC) by 3% and 14%, for SpecInt2000 and SpecFP2000, respectively.

The demand for higher computing power and, thus, more on-chip computing resources; is ever increasing. The size of on-chip cache memory has also been consistently increasing to keep up with developments in implementation technology. However, some applications may not utilize full cache capacity and, on the contrary, require more computing resources. To efficiently utilize silicon real-estate on the chip, we exploit the possibility of using a part of cache memory for computational purposes to strike a balance in the usage of memory and computing resources for various applications. In an earlier part of our work, the idea of adaptive balanced computing (ABC) architecture was evolved, where a module of an L1 data cache is used as a coprocessor controlled by main processor. A part of an L1 data cache is designed as a reconfigurable functional cache (RFC) that can be configured to perform a selective core function in the media application whenever such computing capability is required. ABC architecture provides speedups ranging from 1.04x to 5.0x for various media applications. We show that a reduced number of cache accesses and lesser utilization of other on-chip resources, due to a significant reduction in execution time of application, will result in power savings. For this purpose, we first develops a model to compute the power consumed by the RFC while accelerating the computation of multimedia applications. The results show that up to a 60 percent reduction in power consumption is achieved for MPEG decoding and a reduction in the range of 10 to 20 percent for various other multimedia applications. Besides, beyond the discussions in earlier work on ABC architecture, we present a detailed circuit level implementation of the core functions in the RFC modules. Further, we go much further and study the impact of converting the conventional cache into RFC on both access time and energy consumption. The analysis is performed on a wide spectrum of cache organizations with size varying from 8KB to 256KB for varying set associativity.

IP address lookup algorithms can be evaluated on a number of metrics lookup time, update time, memory usage, and to a lesser extent, the time to construct the data structure used to support lookups and updates. Many of the existing methods are geared towards optimizing a specific metric, and hence do not scale well with the ever expanding routing tables and the forthcoming IPv6 with 128 bit long IP address. In contrast, our effort is directed at simultaneously optimizing multiple metrics and provide solutions that scale well to IPv6. In this paper, we present two IP address lookup schemes Elevator - Stairs algorithm and logW - Elevators algorithm. For a routing table with N prefixes, The Elevator - Stairs algorithm uses optimal O(N) memory, and achieves better lookup and update times than other methods with similar memory requirements. The logW - Elevators algorithm gives O(log W) lookup time, where W is the length of an IP address, while improving upon update time and memory usage. Experimental results using the MAE-West router with 29,487 prefixes show that the Elevator - Stairs algorithm gives an average throughput of 15.7 Million lookups per second (Mlps) using 459 KB of memory, and the logW - Elevators algorithm gives an average throughput of 21.41 Mlps with a memory usage of 1259 KB.

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.

With an immense continuous growth in Internet traffic, the demand for routers that perform IP routing at high speed and throughput is ever increasing. The key issue in the router performance is the IP routing lookup mechanism based on the longest prefix matching scheme. Earlier works on fast IPv4 routing table lookup are based on content addressable memory (CAM), memory lookups and CPU caching. These schemes depend on the memory access technology which limits their performance. Besides, these address lookup schemes designed for the IPv4 32-bit address mostly are not extensible to adapt to the forthcoming IPv6 where the IP address is 128 bits long. The paper presents a binary decision diagrams based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The experimental results show that, for the 32-bit IP address large MAE-east routing table, the number of redundant nodes is more than 99.99% in constructing the binary decision tree. With the binary encoding of the output port, an additional 36% reduction is obtained in the number of effective nodes. Besides the performance of the scheme, issues relating to routing table update and the scalability to IPv6 are discussed.