PHAST is to date one of the fastest algorithms for performing single source shortest path (SSSP) queries on road-network graphs. PHAST operates on graphs produced in part using Geisberger's contraction hierarchy (CH) algorithm. Producing these graphs is time consuming, limiting PHAST's usefulness when graphs are not available in advance. CH iteratively assigns scores to nodes, contracts (removes) the highest-scoring node, and adds shortcut edges to preserve distances. Iteration stops when only one node remains. Scoring and contraction rely on a witness path search (WPS) of nearby nodes. Little work has been reported on parallel and especially GPU CH algorithms. This is perhaps due to issues such as the validity of simultaneous potentially overlapping searches, score staleness, and parallel graph updates.

In an effort to achieve the high prediction accuracy needed to attain high instruction throughputs, branch predictors proposed in the literature and used in real systems have become increasingly more complex and larger over time. This is not consistent with the anticipated trend of simpler and more numerous cores in future multi-core processors. We introduce the Spotlight branch predictor, a novel profile-based predictor which is able to achieve high prediction accuracy despite its simple design. Spotlight achieves high accuracy because complex decisions in the prediction process are made during an OS managed, one-time profile run instead of using complex hardware. We show that Spotlight achieves higher accuracy than Gshare as well as highly accurate and implementable predictors such as YAGS and the hybrid bimodal-Gshare predictor. It achieves an average reduction in misprediction rate of 20% over Gshare, 11% over elastic history buffer, 14% over Yags and 10% over hybrid for a hardware budget of 8 kB. Spotlight is also compared to two difficult to implement neural predictors, the path-based neural and the hashed perceptron. It outperforms the path-based neural predictor at all sizes and the hashed perceptron at smaller hardware budgets. These results demonstrate that a simple profile-based predictor can achieve many of the benefits of more complex predictors. We also show that a single cycle latency implementation of Spotlight can be achieved without sacrificing accuracy by using an upstream replacement scheme.

As chip multiprocessor (CMP) has become the mainstream in processor architectures, Intel and AMD have introduced their dual-core processors to the PC market. In this paper, performance studies on an Intel Core 2 Duo, an Intel Pentium D and an AMD Athlon 64times2 processor are reported. According to the design specifications, key derivations exist in the critical memory hierarchy architecture among these dual-core processors. In addition to the overall execution time and throughput measurement using both multiprogrammed and multi-threaded workloads, this paper provides detailed analysis on the memory hierarchy performance and on the performance scalability between single and dual cores. Our results indicate that for the best performance and scalability, it is important to have (1) fast cache-to-cache communication, (2) large L2 or shared capacity, (3) fast L2 to core latency, and (4) fair cache resource sharing. Three dual-core processors that we studied have shown benefits of some of these factors, but not all of them. Core 2 Duo has the best performance for most of the workloads because of its microarchitecture features such as shared L2 cache. Pentium D shows the worst performance in many aspects due to its technology-remap of Pentium 4.

A Banyan network analysis technique is presented which more accurately models a congested network than other reported techniques. The analysis is based on the observation that a full queue (within the switching modules making up the network) causes traffic to back up. For a short time after becoming full, the free space in the queue is limited to no more than one slot. A queue in such a condition is called congested. Because of blocking the arrival rate to a congested queue is higher; this tends to maintain congestion. The arrival rate to a congested queue's dual is lower, as is the service rate for queues feeding the congested queue. These effects are captured in the analysis by using a state model that codes the condition of a queue and its neighbors. From a queue's state it can be determined if the queue, its dual, or a next-stage queue to which it connects is congested, as well as the number of items in the queue. Network throughput computed with the model is closer to that obtained from simulations than other Banyan analyses appearing in literature, including those designed to model congestion. Further, the queue-occupancy distributions are much closer than other analyses, suggesting that the analysis better models conditions in congested Banyan networks.

New networks, called GLO networks, are constructed by adding bus-like links to omega networks, providing additional capacity between cells on momentarily busy paths. Equivalent pin-count GLO and omega networks offered uniform and nonuniform traffic were simulated. GLO networks exhibited lower latency for nonuniform traffic and light to moderate uniform traffic.

A lower bound on the amount of information necessary to compute the switch settings for a three-stage Clos network is derived. The bound is derived by considering the effect of a family of permutations, called balanced multiloops, on the settings of the switches of a Clos network. By carefully selecting these permutations, it is proven that there exists at least one switch in each stage whose setting depends upon at least (k/spl minus/3)(m/2+1)/2 assignments in the permutations to be routed for k/spl ges/4 where m is the number of center-stage switches and k is the number of input and output-stage switches. It is also proven that the setting of the input stage depends on at least m/spl minus/1 assignments. Lower bounds on the routing time of a three-stage Clos network on a variety of machine models follow immediately from these results. In particular, any constant fan-in implementation of any routing algorithm for such a network should have a time lower bound of /spl Omega/(log mk).>

A method of reducing the volume of data flowing through the network in a shared memory parallel computer (multiprocessor) is described. The reduction is achieved by difference coding the memory addresses in messages sent between processing elements (PE's) and memories. In an implementation, each PE would store the last address sent to each memory, and vice versa. Messages that would normally contain an address instead contain the difference between the address associated with the current and most recent messages. Trace-driven simulation shows that only 70% or less of traffic volume (including data and overhead) is necessary, even in systems using coherent caches. The reduction in traffic could result in a lower cost or lower latency network. The cost of the hardware to achieve this is small, and the delay added is insignificant compared to network latency.>