7460855
Automatic Code Mapping on an Intelligent Memory Architecture
This paper presents an algorithm to automatically map code on a generic intelligent memory system that consists of a high-end host processor and a simpler memory processor. To achieve high performance with this type of architecture, the code needs to be partitioned and scheduled such that each section is assigned to the processor on which it runs most efficiently. In addition, the two processors should overlap their execution as much as possible. With our algorithm, applications are mapped fully automatically using both static and dynamic information. Using a set of standard applications and a simulated architecture, we obtain average speedups of 1.7 for numerical applications and 1.2 for nonnumerical applications over a single host with plain memory. The speedups are very close and often higher than ideal speedups on a more expensive multiprocessor system composed of two identical host processors. Our work shows that heterogeneity can be cost-effectively exploited and represents one step toward effectively mapping code on heterogeneous intelligent memory systems.
3126586
A Constant Propagation Algorithm for Explicitly Parallel Programs
In this paper, we present a constant propagation algorithm for explicitly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation algorithm. Without considering the interaction between threads, classical optimizations lead to an incorrect program transformation for parallel programs. To make analyzing parallel programs possible, a new intermediate representation is needed. We introduce the Concurrent Static Single Assignment (CSSA) form to represent explicitly parallel programs with interleaving semantics and synchronization. The only parallel construct considered in this paper is cobegin/coend. A new confluence function, the π-assignment, which summarizes the information of interleaving statements between threads, is introduced. The Concurrent Control Flow Graph, which contains information about conflicting statements, control flow, and synchronization, is used as an underlying representation for the CSSA from.
14329383
STeP: The Stanford Temporal Prover
We describe the Stanford Temporal Prover (STeP), a system being developed to support the computer-aided formal verification of concurrent and reactive systems based on temporal specifications. Unlike systems based on model-checking, STeP is not restricted to finite-state systems. It combines model checking and deductive methods to allow the verification of a broad class of systems, including programs with infinite data domains, N-process programs, and N-component circuit designs, for arbitrary N. In short, STeP has been designed with the objective of combining the expressiveness of deductive methods with the simplicity of model checking. The verification process is for the most part automatic. User interaction occurs mostly at the highest, most intuitive level, primarily through a graphical proof language of verification diagrams. Efficient simplification methods, decision procedures, and invariant generation techniques are then invoked automatically to prove resulting first-order verification conditions with minimal assistance. We describe the performance of the system when applied to several examples, including the N-process dining philosopher''s program, Szymanski''s N-process mutual exclusion algorithm, and a distributed N-way arbiter circuit.
275005
Using a user-level memory thread for correlation prefetching
This paper introduces the idea of using a User-Level Memory Thread (ULMT) for correlation prefetching. In this approach, a user thread runs on a general-purpose processor in main memory, either in the memory controller chip or in a DRAM chip. The thread performs correlation prefetching in software, sending the prefetched data into the L2 cache of the main processor. This approach requires minimal hardware beyond the memory processor: the correlation table is a software data structure that resides in main memory, while the main processor only needs a few modifications to its L2 cache so that it can accept incoming prefetches. In addition, the approach has wide usability, as it can effectively prefetch even for irregular applications. Finally, it is very flexible, as the prefetching algorithm can be customized by the user on an application basis. Our simulation results show that, through a new design of the correlation table and prefetching algorithm, our scheme delivers good results. Specifically, nine mostly-irregular applications show an average speedup of 1.32. Furthermore, our scheme works well in combination with a conventional processor-side sequential prefetcher, in which case the average speedup increases to 1.46. Finally, by exploiting the customization of the prefetching algorithm, we increase the average speedup to 1.53.
221495
Adaptively Increasing Performance and Scalability of Automatically Parallelized Programs
This paper presents adaptive execution techniques that determine whether automatically parallelized loops are executed parallelly or sequentially in order to maximize performance and scalability. The adaptation and performance estimation algorithms are implemented in a compiler preprocessor. The preprocessor inserts code that automatically determines at compile-time or at run-time the way the parallelized loops are executed. Using a set of standard numerical applications written in Fortran77 and running them with our techniques on a distributed shared memory multiprocessor machine (SGI Origin2000), we obtain the performance of our techniques, on average, 26%, 20%, 16%, and 10% faster than the original parallel program on 32, 16, 8, and 4 processors, respectively. One of the applications runs even more than twice faster than its original parallel version on 32 processors.
2237026
Restructuring programs for high-speed computers with Polaris
The ability to automatically parallelize standard programming languages results in program portability across a wide range of machine architectures. It is the goal of the Polaris project to develop a new parallelizing compiler that overcomes limitations of current compilers. While current parallelizing compilers may succeed on small kernels, they often fail to extract any meaningful parallelism from whole applications. After a study of application codes, it was concluded that by adding a few new techniques to current compilers, automatic parallelization becomes feasible for a range of whole applications. The techniques needed are interprocedural analysis, scalar and array privatization, symbolic dependence analysis, and advanced induction and reduction recognition and elimination, along with run-time techniques to permit the parallelization of loops with unknown dependence relations.
7513516
A monotonic-decreasing rate scheduler for variable-bit-rate video streaming
Variable-bit-rate (VBR) encoded videos can provide a more consistent visual quality than constant-bit-rate (CBR) encoded videos. However, the long-range bit-rate variations in VBR videos make it difficult to efficiently provide quality-of-service control in a video-on-demand system. Existing scheduling algorithms such as Optimal Smoothing, which requires both downward and upward bandwidth reallocations to adapt to the video bit-rate variations, simply cannot guarantee video delivery in networks with mixed video and data traffic. This study tackles this limitation by investigating a new scheduling algorithm with monotonic-decreasing rate allocations for scheduling video data transmissions. By eliminating upward bandwidth reallocations, the proposed scheduler can guarantee video delivery even in the presence of other data traffic in the same network. Moreover, results show that the proposed scheduler can achieve such performance guarantee without tradeoff in performance or resource requirements. This work presents this new monotonic-decreasing rate scheduler, analyzes its fundamental properties, and evaluates its performance using a large number of real-world VBR video traces (274 DVD movies) in extensive trace-driven simulations.
46124956
The formal definition of the BASIC language
The translator The translator which transforms the parsed text into the abstract text (that is, a text which conforms to the abstract syntax and takes into account the default conditions) is peculiar to the language in the Lucas system but has not been developed here since it is the author's opinion that a general translator may be developed which is applicable to all languages. The default rules for Basic are:
10209884
Downlink power allocation for multi-class wireless systems
In this paper we consider a power allocation problem in multi-class wireless systems. We focus on the downlink of the system. Each mobile has a utility function that characterizes its degree of satisfaction for the received service. The objective is to obtain a power allocation that maximizes the total system utility. Typically, natural utility functions for each mobile are nonconcave. Hence, we cannot use existing convex optimization techniques to derive a global optimal solution. We develop a simple (distributed) algorithm to obtain a power allocation that is asymptotically optimal in the number of mobiles. The algorithm is based on dynamic pricing and consists of two stages. At the mobile selection stage, the base station selects mobiles to which power is allocated. At the power allocation stage, the base station allocates power to the selected mobiles. We provide numerical results that illustrate the performance of our scheme. In particular, we show that our algorithm results in system performance that is close to the performance of a global optimal solution in most cases.
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.
26819257
Enumeration of graph embeddings
Abstract For a finite connected simple graph G , let Γ be a group of graph automorphisms of G . Two 2-cell embeddings ι: G → S and j : G → S of a graph G into a closed surface S (orientable or nonorientable) are congruent with respect to Γ if there are a surface homeomorphism h : S → S and a graph automorphism γϵΓ such that h oι= j oγ. In this paper, we give an algebraic characterization of congruent 2-cell embeddings, from which we enumerate the congruence classes of 2-cell embeddings of a graph G into closed surfaces with respect to a group of automorphisms of G , not just the full automorphism group. Some applications to complete graphs are also discussed. As an orientable case, the oriented congruence of a graph G into orientable surfaces with respect to the full automorphism group of G was enumerated by Mull et al. (1988).