15743949
Initial results on the performance and cost of vector microprocessors
Increasingly wider superscalar processors are experiencing diminishing performance returns while requiring larger portions of die area dedicated to control rather than datapath. As an alternative to using these processors to exploit parallelism effectively, we are investigating the viability of using single-chip vector microprocessors. This paper presents some initial results of our investigation where we compare the performance and cost of vector microprocessors to that of aggressive, out-of-order superscalar microprocessors. On the performance side, we show that vector processors are able to execute a highly parallel, integer-based application 1.5-7.3 times faster than superscalar processors can by exploiting parallelism more effectively. This ability stems from the use of vector instructions. Vector instructions exploit parallelism across loop iterations by implicitly re-scheduling operations and temporally localizing the parallelism. Vector instructions also reduce instruction bandwidth by more than an order of magnitude because they express an abundance of parallelism in a compact encoding. On the cost side we show that, to achieve these performance gains, highly parallel, integer-based vector microprocessors are no more costly to implement than existing in-order and out-of-order superscalar microprocessors. One reason for this is that the organization of a vector register file provides tremendous bandwidth without incurring a large area penalty. A second reason is that the control logic for issuing vector instructions is relatively simple. Both the performance gains and cost savings are possible because vector processors rely on a vectorizing compiler, rather than hardware, to detect parallelism and to express it in a compact form to the hardware. These initial results suggest that transferring this functionality to the compiler offers a tremendous performance/cost benefit.
1423815
Simple vector microprocessors for multimedia applications
In anticipation of the emergence of multimedia applications as an important workload, microprocessor companies have augmented their instruction-set architectures with short vector extensions, thus adding basic vector hardware to state-of-the-art superscalar processors. Although a vector architecture may be a good match for multimedia applications, there is growing evidence that the control logic for increasingly complex superscalar processors is difficult to implement, Rather than combining a complex superscalar core with short wide vector hardware, we propose using a much simpler processor design that is similar to traditional vector computers with long vectors and simple control logic for instruction issue. Such a design would use the bulk of its transistors and die area for datapath and registers, and thus lessen the time required to design, implement, and verify control. In this paper we present data that quantifies this trading of control transistors for datapath and register transistors. We demonstrate that a 2-way, in-order vector processor with a vector length of 64 and a vector width of 8 requires no more die area, and possibly significantly less area, than a 4-way, out-of-order superscalar processor with short vector extensions. Furthermore, we show that the simple long vector processor is, on average, 2.7 times faster executing multimedia applications than the superscalar processor; and 1.6 times faster than one with short vector extensions. To explain the reasons for the higher performance, we analyze execution time in terms of dynamic operation count and cycles per operation (CPO). A vector processor executes fewer operations by using vector instructions to stripmine a loop. Moreover, a long vector processor achieves a lower CPO by effectively using parallelism at both the operation and the instruction levels. Thus by reducing both terms of the CPO equation, the simple long vector processor achieves greater performance.
10016971
Improved bottleneck domination algorithms
W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an O(n log n + m)- time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression.
1931080
Between Chaos and Routine: Boundary Negotiating Artifacts in Collaboration
Empirical studies of material artifacts in practice continue to be a rich source of theoretical concepts for CSCW. This paper explores the foundational concept of boundary objects and presents the results of a year-long ethnographic study of collaborative work. This research questions the assumption that artifacts exist necessarily within a web of standardized processes and that disorderly processes should be treated as "special cases". I suggest that artifacts can serve to establish and destabilize protocols themselves and that artifacts can be used to push boundaries rather than merely sailing across them.
18796888
Design and Performance Evaluation of Broadcast Algorithms for Time-Constrained Data Retrieval
We refer "time-constrained services" to those requests that have to be replied to within a certain client-expected time duration. If the answer cannot reach the client within this expected time, the value of the information may seriously degrade or even become useless. On-demand channels may not be able to handle all time-constrained services without degrading the performance. How to handle these services in broadcast channels becomes crucial to balance the load of wireless systems. In this paper, we study this problem and find the minimum number of broadcast channels required for such a task. Also, we propose solutions for this problem when the available channels are insufficient. Our performance result reveals that only a moderate number of channels is required to promote these time-constrained services
2177844
Design, performance analysis, and implementation of a super-scalar video-on-demand system
Despite the availability of video-on-demand (VoD) services in a number of cities around the world, large-scale deployment of VoD services in a metropolitan area is still economically impractical. This study presents a novel super-scalar architecture for building very large-scale and efficient VoD systems. The proposed architecture combines the use of static multicast, dynamic multicast, and intelligent client-side caching to vastly reduce server and network resource requirement. Moreover, in sharp contrast to conventional VoD systems where the system cost increases at least linearly with the system scale, the proposed architecture becomes more efficient as the system scales up and can ultimately be scaled up to serve any number of users while still keeping the startup latency short. This paper presents this new architecture, proposes methods to support interactive playback controls without the need for additional server or client resources, and derives an approximate performance model to relate the startup latency with other system parameters. The performance model is validated using simulation and the architecture is evaluated under various system settings. Lastly, a system implementation is presented and benchmarking results obtained to further verify the architecture, the performance model, and the simulation results.
16722634
Scaling applications to massively parallel machines using Projections performance analysis tool
Some of the most challenging applications to parallelize scalably are the ones that present a relatively small amount of computation per iteration. Multiple interacting performance challenges must be identified and solved to attain high parallel efficiency in such cases. We present case studies involving NAMD, a parallel classic molecular dynamics application for large biomolecular systems, and CPAIMD, Car-Parrinello ab initio molecular dynamics application, and efforts to scale them to large number of processors. Both applications are implemented in Charm++, and the performance analysis was carried out using Projections, the performance visualization/analysis tool associated with Charm++. We showcase a series of optimizations facilitated by Projections. The resultant performance of NAMD led to a Gordon Bell award at SC 2002 with unprecedented speedup on 3000 processors with teraflops level peak performance. We also explore the techniques for applying the performance visualization/analysis tool on future generation extreme-scale parallel machines and discuss the scalability issues with Projections.