bluuebunny/crossref_metadata_2025 huggingface dataset:
Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives
Authors: Rinard Martin
Published: November 2005

As shared-memory multiprocessors become the dominant commodity source of computation, parallelizing compilers must support mainstream computations that manipulate irregular, pointer-based data structures such as lists, trees and graphs, Our experience with a parallelizing compiler for this class of applications shows that their synchronization requirements differ significantly from those of traditional parallel computations. Instead of coarse-grain barrier synchronization, irregular computations require synchronization primitives that support efficient fine-grain atomic operations.The standard implementation mechanism for atomic operations uses mutual exclusion locks. But the overhead of acquiring and releasing locks can reduce the performance. Locks can also consume significant amourtts of memory. Optimistic synchronization primitives such as
load linked/stor conditional
are an attractive alternative. They require no additional memory and eliminate the use of heavyweight blocking synchronization constructs.This paper presents our experience using optimistic synchronization to implement fine-grain atomic operations in the context of a parallelizing compiler for irregular object-based programs. We have implemented two versions of the compiler. One version generates code that uses mutual exclusion locks to make operations execute atomically. The other version uses optimistic synchronization. This paper presents the first published algorithm that enables compilers to automatically generate optimistically synchronized parallel code. The presented experimental results indicate that optimistic synchronization is clearly the superior choice for our set of applications. Our results show that it can significantly reduce the memory consumption and improve the overall performance.
Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code
Authors: Frens Jeremy D. , Wise David S.
Published: November 2005

An elementary, machine-independent, recursive algorithm for matrix multiplication C+=A*B provides implicit blocking at
every
level of the memory hierarchy and tests out faster than classically optimrd code, tracking hand-coded BLAS3 routines. Proof of concept is demonstrated by racing the in-place algorithm against manufacturer's hand-tuned BLAS3 routines; it can win.The recursive code bifurcates naturally at the top level into independent block-oriented processes, that each writes to a disjoint and contiguous region of memory. Experience has shown that the indexing vastly improves the patterns of memory access at all levels of the memory hierarchy, independently of the sizes of caches or pages and without ad hoc programming. It also exposed a weakness in SGI's C compilers that merrily unroll loops for the super-scalar R8000 processor, but do not analogously unfold the base cases of the most elementary recursions. Such deficiencies might deter future programmers from using this rich class of recursive algorithms.
Making C++ concurrent and real-time
Authors: Li Wei , Li Gansheng
Published: November 2005

In this paper, we present an approach to add a base class, Thread, to C++, so that any objects of Thread and its derivations can be executed concurrently. Synchronization and communication between two objects are similar to that of Ada rendezvous. Then we add a separate time constraint module to provide time constraint on the level of method of objects. This information makes the execution of codes in accord with temporal relations of object methods, which is specified in the specification of time constraint. Thus, real-time facilities are also added to C++.
Proposed A.A.S. degree program in educational technology
Authors: Lawlor John M.
Published: November 2005

The increase in technology usage in educational settings has created a demand for low-level technical support. Stimulated by initiatives from federal and state governments, the demand is evident in job postings for technical support personnel in both educational and business environments. In each case, education and/or training aspects are central to these positions. In addition, there is a thriving "cottage industry" for technical support.
Computer support technology
Authors: Matthiesen Pam , Pennington T. S. , Richards Karen
Published: November 2005

The Metropolitan Community Colleges, with the advisement of local business and industry, have implemented a thirty-hour certificate program in Computer Support Technology. The Association for Computing Machinery curriculum guide for two-year colleges in the area of Computer Support Services served as a basis for this development. This certificate program requires a combination of business and technical courses to prepare graduates to work as an entry-level computer technician or help-desk/support person.
Software engineering
Authors: Christiaanse Vance
Published: November 2005

Software engineering is a profession today in the sense that you can get paid for doing it. But it has not yet reached the maturity level many other professions have reached. Here's a viewpoint on where we are and what we can do about it.
A formal approach to the teaching of programming language concepts
Authors: Kitchen Andrew
Published: November 2005

While the power of formal semantics is well recognized, it is not usually considered a teaching tool. This paper describes the use of denotational semantics in a course on programming language design for beginning graduate students. The course introduces the semantic and implementation issues underlying such concepts as naming, block structure, scope rules, parameter passing, flow control, and exception handling. The approach taken is to specify the semantics of these mechanisms, using a simplified form of denotational semantics, and use these descriptions as the basis for discussion. Implementations are developed from the specifications, and are available to students for experimentation.
Detecting memory errors via static pointer analysis (preliminary experience)
Authors: Dor Nurit , Rodeh Michael , Sagiv Mooly
Published: November 2005

Programs which manipulate pointers are hard to debug. Pointer analysis algorithms (originally aimed at optimizing compilers) may provide some remedy by identifying potential errors such as dereferencing NULL pointers by statically analyzing the behavior of programs on all their input data.Our goal is to identify the "core program analysis techniques" that can be used when developing realistic tools which detect memory errors at compile time without, generating too many false alarms. Our preliminary experience indicates that the following techniques are necessary: (i) finding aliases between pointers, (ii) flow sensitive techniques that account, for the program control flow constructs. (iii) partial interpretation of conditional statements, (iv) analysis of the relationships between pointers, and sometimes (v) analysis of the underlying data structures manipulated by the C program.We show that a combination of these techniques can yield better results than those achieved by state of the art tools. Yet it is not clear to us whether our ideas are applicable to large programs.
An empirical investigation of program spectra
Authors: Harrold Mary Jean , Rothermel Gregg , Wu Rui , Yi Liu
Published: November 2005

A variety of expensive software maintenance and testing tasks require a comparison of the behaviors of program versions. Program spectra have recently been proposed as a heuristic for use in performing such comparisons. To assess the potential usefulness of spectra in this context, we conducted an experiment that examined the relationship between program spectra and program behavior, and empirically compared several types of spectra. This paper reports the results of that experiment.
Register promotion by sparse partial redundancy elimination of loads and stores
Authors: Lo Raymond , Chow Fred , Kennedy Robert , Liu Shin-Ming , Tu Peng
Published: November 2005

An algorithm for register promotion is presented based on the observation that the circumstances for promoting a memory location's value to register coincide with situations where the program exhibits partial redundancy between accesses to the memory location. The recent SSAPRE algorithm for eliminating partial redundancy using a sparse SSA representation forms the foundation for the present algorithm to eliminate redundancy among memory accesses, enabling us to achieve both computational and live range optimality in our register promotion results. We discuss how to effect speculative code motion in the SSAPRE framework. We present two different algorithms for performing speculative code motion: the
conservative
speculation algorithm used in the absence of profile data, and the the
profile-driven
speculation algorithm used when profile data are available. We define the static single use (SSU) form and develop the dual of the SSAPRE algorithm, called SSUPRE, to perform the partial redundancy elimination of stores. We provide measurement data on the SPECint95 benchmark suite to demonstrate the effectiveness of our register promotion approach in removing loads and stores. We also study the relative performance of the different speculative code motion strategies when applied to scalar loads and stores.
Data transformations for eliminating conflict misses
Authors: Rivera Gabriel , Tseng Chau-Wen
Published: November 2005

Many cache misses in scientific programs are due to conflicts caused by limited set associativity. We examine two compile-time data-layout transformations for eliminating conflict misses, concentrating on misses occuring on every loop iteration. Inter-variable padding adjusts variable base addresses, while intra-variable padding modifies array dimension sizes. Two levels of precision are evaluated. PADLITE only uses array and column dimension sizes, relying on assumptions about common array reference patterns. PAD analyzes programs, detecting conflict misses by linearizing array references and calculating
conflict distances
between uniformly-generated references. The Euclidean algorithm for computing the
gcd
of two numbers is used to predict conflicts between different array columns for linear algebra codes. Experiments on a range of programs indicate PADLITE can eliminate conflicts for benchmarks, but PAD is more effective over a range of cache and problem sizes. Padding reduces cache miss rates by 16% on average for a 16K direct-mapped cache. Execution times are reduced by 6% on average, with some SPEC95 programs improving up to 15%.
Partial online cycle elimination in inclusion constraint graphs
Authors: Fähndrich Manuel , Foster Jeffrey S. , Su Zhendong , Aiken Alexander
Published: November 2005

Many program analyses are naturally formulated and implemented using inclusion constraints. We present new results on the scalable implementation of such analyses based on two insights: first, that online elimination of cyclic constraints yields orders-of-magnitude improvements in analysis time for large problems; second, that the choice of constraint representation affects the quality and efficiency of online cycle elimination. We present an analytical model that explains our design choices and show that the model's predictions match well with results from a substantial experiment.
Exploiting idle floating-point resources for integer execution
Authors: Sastry S. Subramanya , Palacharla Subbarao , Smith James E.
Published: November 2005

In conventional superscalar microarchitectures with partitioned integer and floating-point resources, all floating-point resources are idle during execution of integer programs. Palacharla and Smith [26] addressed this drawback and proposed that the floating-point subsystem be augmented to support integer operations. The hardware changes required are expected to be fairly minimal.To exploit these idle floating resources, the compiler must identify integer code that can be profitably offloaded to the augmented floating-point subsystem. In this paper, we present two compiler algorithms to do this. The
basic
scheme offloads integer computation to the floating-point subsystem using existing program loads/stores for inter-partition communication. For the SPECINT95 benchmarks, we show that this scheme offloads from 5% to 29% of the total dynamic instructions to the floating-point subsystem. The
advanced
scheme inserts copy instructions and duplicates some instructions to further offload computation. We evaluate the effectiveness of the two schemes using timing simulation. We show that the advanced scheme can offload from 9% to 41% of the total dynamic instructions to the floating-point subsystem. In doing so, speedups from 3% to 23% are achieved over a conventional microarchitecture.
Improving performance by branch reordering
Authors: Yang Minghui , Uh Gang-Ryung , Whalley David B.
Published: November 2005

The conditional branch has long been considered an expensive operation. The relative cost of conditional branches has increased as recently designed machines are now relying on deeper pipelines and higher multiple issue. Reducing the number of conditional branches executed can often result in a substantial performance benefit. This paper describes a code-improving transformation to reorder sequences of conditional branches. First, sequences of branches that can be reordered are detected in the control flow. Second, profiling information is collected to predict the probability that each branch will transfer control out of the sequence. Third, the cost of performing each conditional branch is estimated. Fourth, the most beneficial ordering of the branches based on the estimated probability and cost is selected. The most beneficial ordering often included the insertion of additional conditional branches that did not previously exist in the sequence. Finally, the control flow is restructured to refflect the new ordering. The results of applying the transformation were significant reductions in the dynamic number of instructions and branches, as well as decreases in execution time.
Communication optimizations for parallel C programs
Authors: Zhu Yingchun , Hendren Laurie J.
Published: November 2005

This paper presents algorithms for reducing the communication overhead for parallel C programs that use dynamically-allocated data structures. The framework consists of an analysis phase called
possible-placement analysis
, and a transformation phase called
communication selection
.The fundamental idea of
possible-placement analysis
is to find all possible points for insertion of remote memory operations. Remote reads are propagated upwards, whereas remote writes are propagated downwards. Based on the results of the possible-placement analysis, the
communication selection
transformation selects the "best" place for inserting the communication, and determines if pipelining or blocking of communication should be performed.The framework has been implemented in the EARTH-McCAT optimizing/parallelizing C compiler, and experimental results are presented for five pointer-intensive benchmarks running on the EARTH-MANNA distributed-memory parallel architecture. These experiments show that the communication optimization can provide performance improvements of up to 16% over the unoptimized benchmarks.
Eliminating array bound checking through dependent types
Authors: Xi Hongwei , Pfenning Frank
Published: November 2005

We present a type-based approach to eliminating array bound checking and list tag checking by conservatively extending Standard ML with a restricted form of dependent types. This enables the programmer to capture more invariants through types while type-checking remains decidable in theory and can still be performed efficiently in practice. We illustrate our approach through concrete examples and present the result of our preliminary experiments which support support the feasibility and effectiveness of our approach.
A study of dead data members in C++ applications
Authors: Sweeney Peter F. , Tip Frank
Published: November 2005

Object-oriented applications may contain data members that can be removed from the application without affecting program behavior. Such "dead" data members may occur due to unused functionality in class libraries, or due to the programmer losing track of member usage as the application changes over time. We present a simple and efficient algorithm for detecting dead data members in C++ applications. This algorithm has been implemented using a prototype version of the IBM VisualAge C++ compiler, and applied to a number of realistic benchmark programs ranging from 600 to 58,000 lines of code. For the non-trivial benchmarks, we found that up to 27.3% of the data members in the benchmarks are dead (average 12.5%), and that up to 11.6% of the object space of these applications may be occupied by dead data members at run-time (average 4.4%).
The DrScheme project
Authors: Felleisen Mattias , Findler R. B. , Flatt M. , Krishnamurthi S.
Published: November 2005

DrScheme provides a graphical user interface for editing and interactively evaluating Scheme programs on all major graphical platforms (Windows 95/nt, MacOs, Unix/X). The environment is especially well-suited to beginning programmers because it supports a tower of Scheme subsets. Each level corresponds to a particular stage in a typical introductory Scheme course and implements a stringent set of syntactic checks. The environment also pinpoints run-time exceptions in a graphical manner and implements a mostly functional read-eval-print loop.Dr. Scheme's most advanced component is a powerful static debugger. It permits programmers to inspect programs for potential safety violations before running them. If the debugger discovers a potential problem, it explains the problem by drawing a value-flow graph over the program text. The value-flow graph shows how an inappropriate value may reach a program operation and trigger a run-time check.The development of Dr. Scheme in Scheme validated the strengths of Scheme, but also revealed several weaknesses. To overcome the latter, the underlying Scheme implementation was extended with a class-based object system, a language of program units, and a sophisticated GUI engine. All of these extensions are available to the programmer, who can thus interactively create fully portable, graphical applications.
Fractal structure of random programs
Authors: Kokol Peter , Brest Janez
Published: November 2005

We constructed a generator of random programs and with the comparison of random and ordinary programs we showed that the long range correlation characteristic coefficient can be used as a measure of the semantic structure of software.
Ownership types for flexible alias protection
Authors: Clarke David G. , Potter John M. , Noble James
Published: November 2005

Object-oriented programming languages allow inter-object aliasing. Although necessary to construct linked data structures and networks of interacting objects, aliasing is problematic in that an aggregate object's state can change via an alias to one of its components, without the aggregate being aware of any aliasing.
Ownership types
form a static type system that indicates object ownership. This provides a flexible mechanism to limit the visibility of object references and restrict access paths to objects, thus controlling a system's dynamic topology. The type system is shown to be sound, and the specific aliasing properties that a system's object graph satisfies are formulated and proven invariant for well-typed programs.
Borrow, copy or steal?
Authors: Simons Anthony J. H.
Published: November 2005

Dynamic memory management in C++ is complex, especially across the boundaries of library abstract data types. C++ libraries designed in the orthodox canonical form (OCF) alleviate some of the problems by ensuring that classes which manage any kind of heap structures faithfully copy and delete these. However, in certain common circumstances, OCF heap structures are wastefully copied multiple times. General reference counting is not an option in OCF, since a shared body violates the intended value semantics; although a copy-on-write policy can be made to work with borrowed heap structures. A simpler ownership policy, based on larceny, allows low-level memory manager objects to steal heap structures from temporary variables, in properly isolated circumstances. Various strategies for regulating theft are presented, ranging from pilfer-constructors to locks on heap data. Larceny has similarities with other transfer of ownership patterns, but is more a core implementation technique designed to improve the efficiency and effectiveness of OCF-conformant libraries.
Safe metaclass programming
Authors: Bouraqadi-Saâdani Noury M. N. , Ledoux Thomas , Rivard Fred
Published: November 2005

In a system where classes are treated as first class objects, classes are defined as instances of other classes calledmetaclasses. An important benefit of using metaclasses is the ability to assignpropertiesto classes (e.g. being abstract, being final, tracing particular messages, supporting multiple inheritance), independently from the base-level code. However, when both inheritance and instantiation are explicitly and simultaneously involved, communication between classes and their instances raises themetaclass compatibilityissue. Some languages (such as SMALLTALK) address this issue but do not easily allow the assignment of specific properties to classes. In contrast, other languages (such as CLOS) allow the assignment of specific properties to classes but do not tackle the compatibility issue well.In this paper, we describe a new model of metalevel organization, calledthe compatibility model, which overcomes this difficulty. It allowssafe metaclass programmingsince it makes it possible to assign specific properties to classes while ensuring metaclass compatibility. Therefore, we can take advantage of the expressive power of metaclasses to build reliable software. We extend this compatibility model in order to enable safe reuse and composition of class specific properties. This extension is implemented in NEOCLASSTALK, a fully reflective SMALLTALK.
Data groups
Authors: Leino K. Rustan M.
Published: November 2005

This paper explores the interpretation of specifications in the context of an object-oriented programming language with subclassing and method overrides. In particular, the paper considers annotations for describing what variables a method may change and the interpretation of these annotations. The paper shows that there is a problem to be solved in the specification of methods whose overrides may modify additional state introduced in subclasses. As a solution to this problem, the paper introduces
data groups
, which enable modular checking and rather naturally capture a programmer's design decisions.
Compatible genericity with run-time types for the Java programming language
Authors: Cartwright Robert , Steele Guy L.
Published: November 2005

The most serious impediment to writing substantial programs in the Java™ programming language is the lack of a
gentricity
mechanism for abstracting classes and methods with respect to type. During the past two years, several research groups have developed Java extensions that support various forms of genericity, but none has succeeded in accommodating general type parameterization (akin to Java arrays) while retaining compatibility with the existing. Java Virtual Machine. In this paper, we explain how to support general type parameterization---including both non-variant and covariant subtyping---on top of the existing Java Virtual Machine at the cost of a larger code footprint and the forwarding of some method calls involving parameterized classes and methods. Our language extension is forward and backward compatible with the Java 1.2 language and run-time environment: programs in the extended language will run on existing Java 1.2 virtual machines (relying only on the unparameterized Java core libraries) and all existing Java 1.2 programs have the same binary representation and semantics (behavior) in the extended language.
Visualizing dynamic software system information through high-level models
Authors: Walker Robert J. , Murphy Gail C. , Freeman-Benson Bjorn , Wright Darin , Swanson Darin , Isaak Jeremy
Published: November 2005

Dynamic information collected as a software system executes can help software engineers perform some tasks on a system more effectively. To interpret the sizable amount of data generated from a system's execution, engineers require tool support. We have developed an off-line, flexible approach for visualizing the operation of an object-oriented system at the architectural level. This approach complements and extends existing profiling and visualization approaches available to engineers attempting to utilize dynamic information. In this paper, we describe the technique and discuss preliminary qualitative studies into its usefulness and usability. These studies were undertaken in the context of performance tuning tasks.
Object lessons learned from a distributed system for remote building monitoring and operation
Authors: Olken Frank , Jacobsen Hans-Arno , McParland Chuck , Piette Mary Ann , Anderson Mary F.
Published: November 2005

In this paper we describe our experiences with the design, the deployment, and the initial operation of a distributed system for the remote monitoring and operation of multiple heterogeneous commercial buildings across the Internet from a single control center. Such systems can significantly reduce building energy usage.Our system is distinguished by its ability to interface to multiple heterogeneous legacy building Energy Management Control Systems (EMCSs), its use of the Common Object Request Broker Architecture (CORBA) standard communication protocols for the former task, development of a standardized naming system for monitoring points in buildings, the use of a relational DBMS to store and process time series data, automatic time and unit conversion, and a scripted time series visualization system.We describe our design choices and our experiences in development and operation. We note requirements for future distributed systems software for interoperability of heterogeneous real-time data acquisition and control systems.
Vclusters
Authors: Mcauliffe Mark L. , Carey Michael J. , Solomon Marvin H.
Published: November 2005

We consider the problem of delivering an effective fine-grained clustering tool to implementors and users of object-oriented database systems. This work emphasizes on-line clustering
mechanisms
, as contrasted with earlier work that concentrates on clustering
policies
(deciding which objects should be near each other). Existing on-line clustering methods can be ineffective and/or difficult to use and may lead to poor space utilization on disk and in the disk block cache, particularly for small- to medium-size groups of objects. We introduce variable-size clusters (
Vclusters
), a fine-grained object clustering architecture that can be used directly or as the target of an automatic clustering algorithm. We describe an implementation of Vclusters in the Shore OODBMS and present experimental results that show that Vclusters significantly outperform other mechanisms commonly found in object database systems (fixed-size clusters and near hints). Vclusters deliver excellent clustering and space utilization with only a modest cost for maintaining clustering during updates.
Putting more meaning in expressions
Authors: Bantchev Boyko B.
Published: November 2005

The paper discusses the usefulness of expression orientedness for procedural languages. Several constructs are proposed that enrich the semantics of expressions in expression-oriented languages. The aim is to extend the possibilities for explicit specification of properties and interrelations between program objects, thus conveying more meaning to the reader of a program. Finally, some concluding considerations are made, in the form of general rules for explicit and straightforward program coding.
Reducing garbage in Java
Authors: McDowell C. E.
Published: November 2005

One of the important advantages of Java, from a programmers prospective, is the use of garbage collection. One aspect of memory management in Java is that all objects are created on a garbage collected heap. Only primitive types, mostly numeric types and references to objects, are allocated on the runtime stack. We speculated that a significant number of objects behaved like traditional automatic variables, that are normally allocated on the runtime stack. We instrumented a Java virtual machine to test this hypothesis. The percentage of objects that could have been allocated on a stack instead of on the heap ranged from zero to possibly as high as 56%, but were generally in the 5--15% range.
Schedule-independent storage mapping for loops
Authors: Strout Michelle Mills , Carter Larry , Ferrante Jeanne , Simon Beth
Published: November 2005

This paper studies the relationship between storage requirements and performance. Storage-related dependences inhibit optimizations for locality and parallelism. Techniques such as renaming and array expansion can eliminate all storage-related dependences, but do so at the expense of increased storage. This paper introduces the
universal occupancy vector
(UOV) for loops with a regular stencil of dependences. The UOV provides a schedule-independent storage reuse pattern that introduces no further dependences (other than those implied by true flow dependences). OV-mapped code requires less storage than full array expansion and only slightly more storage than schedule-dependent minimal storage.We show that determine if a vector is a UOV is NPcomplete. However, an easily constructed but possibly nonminimal UOV can be used. We also present a branch and bound algorithm which finds the minimal UOV, while still maintaining a legal UOV at all times.Our experimental results show that the use of OV-mapped storage, coupled with tiling for locality, achieves better performance than tiling after array expansion, and accommodates larger problem sizes than untilable, storage-optimized code. F'urthermore, storage mapping based on the UOV introduces negligible runtime overhead.
Data speculation support for a chip multiprocessor
Authors: Hammond Lance , Willey Mark , Olukotun Kunle
Published: November 2005

Thread-level speculation is a technique that enables parallel execution of sequential applications on a multiprocessor. This paper describes the complete implementation of the support for threadlevel speculation on the Hydra chip multiprocessor (CMP). The support consists of a number of software speculation control handlers and modifications to the shared secondary cache memory system of the CMP This support is evaluated using five representative integer applications. Our results show that the speculative support is only able to improve performance when there is a substantial amount of medium--grained loop-level parallelism in the application. When the granularity of parallelism is too small or there is little inherent parallelism in the application, the overhead of the software handlers overwhelms any potential performance benefits from speculative-thread parallelism. Overall, thread-level speculation still appears to be a promising approach for expanding the class of applications that can be automatically parallelized, but more hardware intensive implementations for managing speculation control are required to achieve performance improvements on a wide class of integer applications.
Active disks
Authors: Acharya Anurag , Uysal Mustafa , Saltz Joel
Published: November 2005

Several application and technology trends indicate that it might be both profitable and feasible to move computation closer to the data that it processes. In this paper, we evaluate
Active Disk
architectures which integrate significant processing power and memory into a disk drive and allow application-specific code to be downloaded and executed on the data that is being read from (written to) disk. The key idea is to offload bulk of the processing to the diskresident processors and to use the host processor primarily for coordination, scheduling and combination of results from individual disks. To program Active Disks, we propose a stream-based programming model which allows disklets to be executed efficiently and safely. Simulation results for a suite of six algorithms from three application domains (commercial data warehouses, image processing and satellite data processing) indicate that for these algorithms, Active Disks outperform conventional-disk architectures.
A cost-effective, high-bandwidth storage architecture
Authors: Gibson Garth A. , Nagle David F. , Amiri Khalil , Butler Jeff , Chang Fay W. , Gobioff Howard , Hardin Charles , Riedel Erik , Rochberg David , Zelenka Jim
Published: November 2005

This paper describes the Network-Attached Secure Disk (NASD) storage architecture, prototype implementations oj NASD drives, array management for our architecture, and three, filesystems built on our prototype. NASD provides scalable storage bandwidth without the cost of servers used primarily, for transferring data from peripheral networks (e.g. SCSI) to client networks (e.g. ethernet). Increasing datuset sizes, new attachment technologies, the convergence of peripheral and interprocessor switched networks, and the increased availability of on-drive transistors motivate and enable this new architecture. NASD is based on four main principles: direct transfer to clients, secure interfaces via cryptographic support, asynchronous non-critical-path oversight, and variably-sized data objects. Measurements of our prototype system show that these services can be cost-effectively integrated into a next generation disk drive ASK. End-to-end measurements of our prototype drive andfilesysterns suggest that NASD cun support conventional distributed filesystems without performance degradation. More importantly, we show scaluble bandwidth for NASD-specialized filesystems. Using a parallel data mining application, NASD drives deliver u linear scaling of 6.2 MB/s per clientdrive pair, tested with up to eight pairs in our lab.
Performance counters and state sharing annotations
Authors: Weissman Boris
Published: November 2005

This paper describes a combined approach for improving thread locality that uses the bardware performance monitors of modem processors and program-centric code annotations to guide thread scheduling on SMPs. The approach relies on a shared state cache model to compute expected thread footprints in the cache on-line. The accuracy of the model has been analyzed by simmations involving a set of parallel applications. We demonstrate how the cache model can be used to implement several practical locality-based thread scheduling policies with little overhead. Active Threads, a portable, high-performance thread system, has been built and used to investigate the performance impact of locality scheduling for several applications.
Performance isolation
Authors: Verghese Ben , Gupta Anoop , Rosenblum Mendel
Published: November 2005

Shared-memory multiprocessors (SMPs) are being extensively used as general-purpose servers. The tight coupling of multiple processors, memory, and I/O provides enormous computing power in a single system, and enables the efficient sharing of these resources.The operating systems for these machines (UNIX or Windows NT) provide very few controls for sharing the resources of the system among the active tasks or users. This unconstrained sharing model is a serious limitation for a server because the load placed by one user can adversely affect other users' performance in an unpredictable manner. We show that this lack of isolation is caused by the resource allocation scheme (or lack thereof) carried over from singleuser workstations. Multi-user multiprocessor systems require more sophisticated resource management, and we show how the proposed "performance isolation" scheme can address the current weaknesses of these systems. We have implemented performance isolation in the Silicon Graphics IRIX operating system for three important system resources: CPU time, memory, and disk bandwidth. Running a number of workloads we show that our proposed scheme is successful at providing workstation-like isolation under heavy load, SMP-like latency under light load, and SMP-like throughput in all cases.
Locality-aware request distribution in cluster-based network servers
Authors: Pai Vivek S. , Aron Mohit , Banga Gaurov , Svendsen Michael , Druschel Peter , Zwaenepoel Willy , Nahum Erich
Published: November 2005

We consider cluster-based network servers in which a front-end directs incoming requests to one of a number of back-ends. Specifically, we consider
content-based request distribution:
the front-end uses the content requested, in addition to information about the load on the back-end nodes, to choose which back-end will handle this request. Content-based request distribution can improve locality in the back-ends' main memory caches, increase secondary storage scalability by partitioning the server's database, and provide the ability to employ back-end nodes that are specialized for certain types of requests.As a specific policy for content-based request distribution, we introduce a simple, practical strategy for
locality-aware
request distribution (LARD). With LARD, the front-end distributes incoming requests in a manner that achieves high locality in the back-ends' main memory caches as well as load balancing. Locality is increased by dynamically subdividing the server's working set over the back-ends. Trace-based simulation results and measurements on a prototype implementation demonstrate substantial performance improvements over state-of-the-art approaches that use only load information to distribute requests. On workloads with working sets that do not fit in a single server node's main memory cache, the achieved throughput exceeds that of the state-of-the-art approach by a factor of two to four.With content-based distribution, incoming requests must be handed off to a back-end in a manner transparent to the client,
after
the front-end has inspected the content of the request. To this end, we introduce an efficient
TCP handoflprotocol
that can hand off an established TCP connection in a client-transparent manner.
Accelerating multi-media processing by implementing memoing in multiplication and division units
Authors: Citron Daniel , Feitelson Dror , Rudolph Larry
Published: November 2005

This paper proposes a technique that enables performing multi-cycle (multiplication, division, square-root …) computations in a single cycle. The technique is based on the notion of memoing: saving the input and output of previous calculations and using the output if the input is encountered again. This technique is especially suitable for Multi-Media (MM) processing. In MM applications the local entropy of the data tends to be low which results in repeated operations on the same datum.The inputs and outputs of assembly level operations are stored in cache-like lookup tables and accessed in parallel to the conventional computation. A successful lookup gives the result of a multi-cycle computation in a single cycle, and a failed lookup doesn't necessitate a penalty in computation time.Results of simulations have shown that on the average, for a modestly sized memo-table, about 40% of the floating point multiplications and 50% of the floating point divisions, in Multi-Media applications, can be avoided by using the values within the memo-table, leading to an average computational speedup of more than 20%.
Value speculation scheduling for high performance processors
Authors: Fu Chao-Ying , Jennings Matthew D. , Larin Sergei Y. , Conte Thomas M.
Published: November 2005

Recent research in value prediction shows a surprising amount of predictability for the values produced by register-writing instructions. Several hardware based value predictor designs have been proposed to exploit this predictability by eliminating flow dependencies for highly predictable values. This paper proposed a hardware and software based scheme for value speculation scheduling (VSS). Static VLIW scheduling techniques are used to speculate value dependent instructions by scheduling them above the instructions whose results they are dependent on. Prediction hardware is used to provide value predictions for allowing the execution of speculated instructions to continue. In the case of miss-predicted values, control flow is redirected to patch-up code so that execution can proceed with the correct results. In this paper, experiments in VSS for load operations in the SPECint95 benchmarks are performed. Speedup of up to 17% has been shown for using VSS. Empirical results on the value predictability of loads, based on value profiling data, are also provided.
A non-deterministic call-by-need lambda calculus
Authors: Kutzner Arne , Schmidt-Schauß Manfred
Published: November 2005

In this paper we present a non-deterministic call-by-need (untyped) lambda calculus λndwith a constant choice and a let-syntax that models sharing. Our main result is that λndhas the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambda-lifting using deterministic maximal free expressions. These results show that λndis a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation.An intended application of λndis as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
Garbage collection in generic libraries
Authors: Nishanov Gor V. , Schupp Sibylle
Published: November 2005

This paper demonstrates a unified and garbage-collector independent way to describe the information required for precise collection. Thereby it is possible to construct, a library that can be used with various garbage collectors, without modifying the code of the library or the collector itself. The library design presented applies the adaptor idiom of generic programming which guarantees no overhead incurred if the library is used with manual allocators or with garbage collectors that do not require programmer cooperation. As an illustration of our approach we provide sample adaptors for Bartlett's and CMM primary collectors. We also show that the Standard Template Library (STL) can be easily modified to become garbage-collector aware.
Compiler support to customize the mark and sweep algorithm
Authors: Colnet Dominique , Coucaud Philippe , Zendra Olivier
Published: November 2005

Mark and sweep garbage collectors (GC) are classical but still very efficient automatic memory management systems. Although challenged by other kinds of systems, such as copying collectors, mark and sweep collectors remain among the best in terms of performance.This paper describes our implementation of an efficient mark and sweep garbage collector tailored to each program. Compiler support provides the type information required to statically and automatically generate this customized garbage collector. The segregation of objects by type allows the production of a more efficient GC code. This technique, implemented in Small Eiffel, our compiler for the object-oriented language Eiffel, is applicable to other languages and other garbage collection algorithms, be they distributed or not.We present the results obtained on programs featuring a variety of programming styles and compare our results to a well-know and high quality garbage collector.
A brief introduction to regions
Authors: Tofte Mads
Published: November 2005

The paper gives an overview of region-based memory management. The emphasis of the paper is on the dynamic aspects of execution, specifically memory management. We illustrate how three static program analyses can be used for inferring memory management directives. They are
region inference, physical size inference
, and
storage mode analysis
. We describe these analyses for a skeletal language inspired by Standard ML. We also describe a region-based runtime system for the skeletal language, based on the runtime system of the ML Kit with Regions.
Cache-conscious structure layout
Authors: Chilimbi Trishul M. , Hill Mark D. , Larus James R.
Published: November 2005

Hardware trends have produced an increasing disparity between processor speeds and memory access times. While a variety of techniques for tolerating or reducing memory latency have been proposed, these are rarely successful for pointer-manipulating programs.This paper explores a complementary approach that attacks the source (poor reference locality) of the problem rather than its manifestation (memory latency). It demonstrates that careful data organization and layout provides an essential mechanism to improve the cache locality of pointer-manipulating programs and consequently, their performance. It explores two placement techniques---clusteringandcoloring---that improve cache performance by increasing a pointer structure's spatial and temporal locality, and by reducing cache-conflicts.To reduce the cost of applying these techniques, this paper discusses two strategies---cache-conscious reorganizationandcache-conscious allocation---and describes two semi-automatic tools---ccmorph and ccmalloc---that use these strategies to produce cache-conscious pointer structure layouts. ccmorph is a transparent tree reorganizer that utilizes topology information to cluster and color the structure. ccmalloc is a cache-conscious heap allocator that attempts to co-locate contemporaneously accessed data elements in the same physical cache block. Our evaluations, with microbenchmarks, several small benchmarks, and a couple of large real-world applications, demonstrate that the cache-conscious structure layouts produced by ccmorph and ccmalloc offer large performance benefits---in most cases, significantly outperforming state-of-the-art prefetching.
Cache-conscious structure definition
Authors: Chilimbi Trishul M. , Davidson Bob , Larus James R.
Published: November 2005

A program's cache performance can be improved by changing the organization and layout of its data---even complex, pointer-based data structures. Previous techniques improved the cache performance of these structures by arranging distinct instances to increase reference locality. These techniques produced significant performance improvements, but worked best for small structures that could be packed into a cache block.This paper extends that work by concentrating on the internal organization of fields in a data structure. It describes two techniques---
structure splitting
and
field reordering
---that improve the cache behavior of structures larger than a cache block. For structures comparable in size to a cache block, structure splitting can increase the number of hot fields that can be placed in a cache block. In five Java programs, structure splitting reduced cache miss rates 10--27% and improved performance 6--18% beyond the benefits of previously described cache-conscious reorganization techniques.For large structures, which span many cache blocks, reordering fields, to place those with high temporal affinity in the same cache block can also improve cache utilization. This paper describes bbcache, a tool that recommends C structure field reorderings. Preliminary measurements indicate that reordering fields in 5 active structures improves the performance of Microsoft SQL Server 7.0 2--3%.