The Capacitated Vehicle Routing Problem (CVRP) is one of the most relevant optimization problems in operations research and logistics nowadays. While current state-of-the-art solutions to this problem implement evolutionary approaches such as Genetic Algorithms (GAs) on GPUs and multi-core CPUs, this work focuses on implementing a GA for CVRP on a high-performance FPGA to achieve an improved calculation efficiency: While maintaining a comparable solution quality and speed, the FPGA consumes only a fraction of the energy required by traditional computing platforms. This is achieved through leveraging algorithmic parallelism by a custom-fitted hardware architecture, combined with customized data representation for efficient processing.

Lookup operations for in-memory databases are heavily memory bound, because they often rely on pointer-chasing linked data structure traversals. They also have many branches that are hard-to-predict due to random key lookups. In this study, we show that although cache misses are the primary bottleneck for these applications, without a method for eliminating the branch mispredictions only a small fraction of the performance benefit is achieved through prefetching alone. We propose the Node Tracker (NT), a novel programmable prefetcher/pre-execution unit that is highly effective in exploiting inter key-lookup parallelism to improve single-thread performance. We extend NT with branch outcome streaming (BOS) to reduce branch mispredictions and show that this achieves an extra 3× speedup. Finally, we evaluate the NT as a pre-execution unit and demonstrate that we can further improve the performance in both single- and multi-threaded execution modes. Our results show that, on average, NT improves single-thread performance by 4.1× when used as a prefetcher; 11.9× as a prefetcher with BOS; 14.9× as a pre-execution unit and 18.8× as a pre-execution unit with BOS. Finally, with 24 cores of the latter version, we achieve a speedup of 203× and 11× over the single-core and 24-core baselines, respectively.

Indirect memory accesses have irregular access patterns that limit the performance of conventional software and hardware-based prefetchers. To address this problem, we propose the Array Tracking Prefetcher (ATP), which tracks array-based indirect memory accesses using a novel combination of software and hardware. ATP is first configured by special metadata instructions, which are inserted by programmer or compiler to pass data structure traversal knowledge. It then calculates and issues prefetches based on this information. ATP also employs a novel mechanism for dynamically adjusting prefetching distance to reduce early or late prefetches. ATP yields average speedup of 2.17 as compared to a single-core without prefetching. By contrast, the speedup for conventional software and hardware-based prefetching is 1.84 and 1.32, respectively. For four cores, the average speedup for ATP is 1.85, while the corresponding speedups for software and hardware-based prefetching are 1.60 and 1.25, respectively.

Indirect memory accesses have irregular access patterns and concomitantly poor spatial locality. To address this problem, we propose the Array Tracking Prefetcher which tracks array-based indirect memory accesses using a novel combination of software and hardware. Our results show that ATP yields average speedup of 1.60 over the baseline single-core without prefetching. By contrast, the speedup for conventional software and hardware-based prefetching, is 1.49 and 1.16, respectively. For four-cores, the average speedups for ATP, software, and hardware are 1.49, 1.38, and 1.11, respectively.

Welcome to the 2015 IEEE International Conference on Networking, Architecture and Storage (NAS)! This is a special occasion for NAS because for the first time it is in the United States, here in Boston, Massachusetts. Boston is renowned for its cultural facilities and world-class educational institutions, as well as its place at the very forefront of American history. On behalf of the NAS 2015 organizing committee, I welcome you to Boston and hope that you get a chance to explore this wonderful city and enjoy its vibrant atmosphere.

This paper covers the design and FPGA-based prototyping of a full-featured multi-core platform for use in computer architecture research studies. Existing platforms for performing studies include software simulators and hardware-assisted simulators, but there are no modular full-hardware platforms designed to measure a wide range of performance metrics. Such a platform, using HDL synthesis onto an FPGA, can run orders of magnitude faster than software-based solutions at the cost of having less flexible processor configuration and implementation. This paper presents an end-to-end solution, from bottom-level hardware design all the way to automated results collection and analysis, which can be used with inexpensive commodity hardware.

Branch prediction accuracy remains to be critical for high performance and low power. Prior work has studied causes of branch mispredictions in order to provide insights into how better branch predictors can be designed. However, most of the previous works have only considered run-time classification of branch mispredictions, leaving a large number of mispredictions in an unknown category. For more comprehensive analysis, in this paper, we present a detailed source code analysis of branch mispredictions for SPEC CPU 2000 and Mibench benchmarks. Our analysis show that constant loop exits, insufficient history lengths, wrong-type history, array access/pointer references, complex linked list data structures, changing function inputs, and varying loop counts are the major causes for most of the branch mispredictions. We further show that most mispredictions have repetitive patterns that suggest different design strategies for future branch predictors.

Although high branch prediction accuracy is necessary for high performance, it typically comes at the cost of larger predictor tables and/or more complex prediction algorithms. Unfortunately, large predictor tables and complex algorithms require more chip area and have higher power consumption, which precludes their use in embedded processors. As an alternative to large, complex branch predictors, in this paper, we investigate adding complementary branch predictors (CBP) to embedded processors to reduce their power consumption and/or improve their branch prediction accuracy. A CBP differs from a conventional branch predictor in that it focuses only on frequently mispredicted branches while letting the conventional branch predictor predict the more predictable ones. Our results show that adding a small 16-entry (28 byte) CBP reduces the branch misprediction rate of static, bimodal, and gshare branch predictors by an average of 51.0%, 42.5%, and 39.8%, respectively, across 38 SPEC 2000 and MiBench benchmarks. Furthermore, a 256-entry CBP improves the energy-efficiency of the branch predictor and processor up to 97.8% and 23.6%, respectively. Finally, in addition to being very energy-efficient, a CBP can also improve the processor performance and, due to its simplicity, can be easily added to the pipeline of any processor.

Due to the long simulation time of the reference input set, computer architects often use reduced time simulation techniques to shorten the simulation time. However, what has not yet been thoroughly evaluated is the accuracy of these techniques relative to the reference input set and with respect to each other. To rectify this deficiency, this paper uses three methods to characterize reduced input set, truncated execution, and sampling-based simulation techniques while also examining their speed versus accuracy trade-off and configuration dependence. Our results show that the three sampling-based techniques, SimPoint, SMARTS, and random sampling, have the best accuracy, the best speed versus accuracy trade-off, and the least configuration dependence. On the other hand, the reduced input set and truncated execution simulation techniques had generally poor accuracy, were not significantly faster than the sampling-based techniques, and were severely configuration dependent. The final contribution of this paper is a decision tree, which can help architects choose the most appropriate technique for their simulations.

High-performance multiprocessor systems built around out-of-order processors with aggressive branch predictors execute many memory references that turn out to be on a mispredicted branch path. Previous work that focused on uniprocessors showed that these wrong-path memory references may pollute the caches by bringing in data that are not needed on the correct execution path and by evicting useful data or instructions. Additionally, they may also increase the amount of cache and memory traffic. On the positive side, however, they may have a prefetching effect for memory references on the correct path. While computer architects have thoroughly studied the impact of wrong-path effects in uniprocessor systems, there is no previous work on its effects in multiprocessor systems. In this paper, we explore the effects of wrong-path memory references on the memory system behavior of shared-memory multiprocessor (SMP) systems for both broadcast and directory-based cache coherence. Our results show that these wrong-path memory references can increase the amount of cache-to-cache transfers by 32%, invalidations by 8% and 20% for broadcast and directory-based SMPs, respectively, and the number of writebacks by up to 67% for both systems. In addition to the extra coherence traffic, wrong-path memory references also increase the number of cache line state transitions by 21% and 32 % for broadcast and directory-based SMPs, respectively. In order to reduce the performance impact of these wrong-path memory references, we introduce two simple mechanisms - filtering wrong-path blocks that are not likely-to-be-used and wrong-path aware cache replacement - that yield speedups of up to 37%.

Due to the simulation time of the reference input set, architects often use alternative simulation techniques. Although these alternatives reduce the simulation time, what has not been evaluated is their accuracy relative to the reference input set, and with respect to each other. To rectify this deficiency, this paper uses three methods to characterize the reduced input set, truncated execution, and sampling simulation techniques while also examining their speed versus accuracy trade-off and configuration dependence. Finally, to illustrate the effect that a technique could have on the apparent speedup results, we quantify the speedups obtained with two processor enhancements. The results show that: 1) the accuracy of the truncated execution techniques was poor for all three characterization methods and for both enhancements, 2) the characteristics of the reduced input sets are not reference-like, and 3) SimPoint and SMARTS, the two sampling techniques, are extremely accurate and have the best speed versus accuracy trade-offs. Finally, this paper presents a decision tree which can help architects choose the most appropriate technique for their simulations.

The speculated execution of threads in a multithreaded architecture, plus the branch prediction used in each thread execution unit, allows many instructions to be executed speculatively, that is, before it is known whether they actually needed by the program. In this study, we examine how the load instructions executed on what turn out to be incorrectly executed program paths impact the memory system performance. We find that incorrect speculation (wrong execution) on the instruction and thread-level provides an indirect prefetching effect for the later correct execution paths and threads. By continuing to execute the mispredicted load instructions even after the instruction or thread-level control speculation is known to be incorrect, the cache misses observed on the correctly executed paths can be reduced by 16 to 73 percent, with an average reduction of 45 percent. However, we also find that these extra loads can increase the amount of memory traffic and can pollute the cache. We introduce the small, fully associative wrong execution cache (WEC) to eliminate the potential pollution that can be caused by the execution of the mispredicted load instructions. Our simulation results show that the WEC can improve the performance of a concurrent multithreaded architecture up to 18.5 percent on the benchmark programs tested, with an average improvement of 9.7 percent, due to the reductions in the number of cache misses.

This paper considers the problem of routing and wavelength assignment (RWA) in optical passive star networks with non-uniform traffic load. The problem can be considered as designing a logical topology over an optical passive star physical topology with a given non-uniform traffic. The approach uses the bipartite graphs and the concept of time and wavelength division multiplexing (TWDM) embedding process to discuss the problem. The non-uniformity of the traffic load makes the logical design computationally hard and requires heuristic algorithms. Then, a linear program can solve the routing. We present an algorithm for effectively assigning a limited number of wavelengths among the access nodes of a WDM multi-hop network, which are connected via a passive star topology. The RWA problem for such a network with non-uniform traffic load is discussed for the first time. The idea is based on reducing the maximum load on each wavelength by using more wavelengths available. The proposed algorithm is tested on several traffic models, and results are given to show the improvement in the performance of the network using our algorithm.