bluuebunny/crossref_metadata_2025 huggingface dataset:
Automatic loop interchange
Authors: Allen Randy , Kennedy Ken
Published: November 2005

Parallel and vector machines are becoming increasingly important to many computation intensive applications. Effectively utilizing such architectures, particularly from sequential languages such as Fortran, has demanded increasingly sophisticated compilers. In general, a compiler needs to significantly reorder a program in order to generate code optimal for a specific architecture.Because DO loops typically control the execution of a number of statements, the order in which loops are executed can dramatically affect the performance of a machine on a particular section of code. In particular,
loop interchange
can often be used to enhance the performance of code on parallel or vector machines.Determining when loops may be safely and profitably interchanged requires a study of the
data dependences
in the program. This work discusses specific applications of that theory to loop interchange. This theory is described as it has been implemented in PFC (Parallel Fortran Converter) -- a program which attempts to uncover operations in sequential Fortran code that may be safely rewritten as vector operations.
Global register allocation at link time
Authors: Wall David W.
Published: November 2005

In previous work in global register allocation, the compiler colors a conflict graph constructed from liveness dataflow information, in order to allocate the same register to many variables that are not simultaneously live. If two procedures are in separately compiled modules, however, the compiler must do this allocation separately for each procedure. As a result, the two procedures might use different registers for the same global, or the same register for different locals.We can remove these problems if we delay the register allocation until link time. Our compiler produces object modules that can be linked and run without global register allocation, but includes with each object module a body of information describing how the module uses variables and procedures. A link-time register allocator then decides which variables are used most frequently, selects registers for them, and rewrites the code to reflect the decision that these variables reside in registers rather than in memory. Construction of the call graph allows us to use the same register for locals of procedures that are not simultaneously active, giving us most of the advantages of a full-scale coloring without the expense.When we use our method for 52 registers, our benchmarks speed up by 10 to 25 percent. Even with only 8 registers, the speedup can be nearly that large if we use previously collected profile information to guide the allocation. We cannot do much better, because programs whose variables all fit in registers rarely speed up by more than 30%. Moreover, profiling shows us that we usually remove 60% to 90% of the loads and stores of scalar variables that the program performs during its execution, and often much more.
Register windows vs. register allocation
Authors: Wall David W.
Published: November 2005

A large register set can be exploited by keeping variables and constants in registers instead of in memory. Hardware register windows and compile-time or link-time global register allocation are ways to do this. A measure of the effectiveness of any of these register management schemes is how thoroughly they remove loads and stores. This measure must also count extra loads and stores executed because of window overflow or conflicts between procedures.By combining profiling, instrumentation, and in-line simulation, we measured the effectiveness of several register management schemes. These included compile-time and link-time schemes for allocating registers, and register window schemes using fixed-size or variable-sized windows. Link-time allocation based on profile information was the clear winner in some cases and did about as well as windows in the rest. Even link-time allocation based on an estimated profile was about as good as windows. Variable-sized windows sometimes did better than fixed-sized windows, but the difference was usually small.Register windows require extra logic in the data path, which may slow the machine cycle slightly, and often use more chip real estate for additional registers. Proponents of windows suppose that they trade these drawbacks for a reduction in the number of memory references they must make. Our results show that this tradeoff should be made the other way. Keep the hardware simple, because a link-time register allocator can nearly duplicate the improvement in memory reference frequency. Then the cycle time can be as small as possible, resulting in faster programs overall.
On-the-fly detection of access anomalies
Authors: Schonberg Edith
Published: November 2005

Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called
merging
and
subtraction
. Upper bounds on storage are shown to be
V
x
N
2
for merging and
V
x
N
for subtraction.
Fast breakpoints
Authors: Kessler Peter B.
Published: November 2005

In re-implementing fast breakpoints for stock hardware, I discovered the joys of putting self-modifying code to good use.By "fast breakpoints" I mean inserting transfers of control to change the behavior of a running program. I don't claim to have invented fast breakpoints: I have traced their use back to 1951 [1]. I didn't even put these breakpoints to novel uses. All I did was rediscover how easy it is to take statically compiled code and modify it at runtime to alter the semantics of programs. The most obvious application is to evaluate predicates and expressions for debugging, but other uses are possible.We have designed and implemented a fast breakpoint facility. Breakpoints are usually thought of as a feature of an interactive debugger, in which case the breakpoints need not be particularly fast. In our environment breakpoints are often used for non-interactive information gathering; for example, procedure call count and statement execution count profiling [Swinehart, et al.]. When used non-interactively, breakpoints should be as fast as possible, so as to perturb the execution of the program as little as possible. Even in interactive debuggers, a conditional breakpoint facility would benefit from breakpoints that could transfer to the evaluation of the condition rapidly, and continue expeditiously if the condition were not satisfied. Such conditional breakpoints could be used to check assertions,
etc.
Program advising could also make use of fast breakpoints [Teitelman]. Examples of advising include tracing, timing, and even animation, all of which should be part of an advanced programming environment.We have ported the Cedar environment from a machine with microcode support for breakpoints [Lampson and Pier] to commercial platforms running C code [Atkinson, et al.]. Most of our ports run under the Unix* operating system, so one choice for implementing breakpoints for Cedar was to use the breakpoint facility provided by that system. The breakpoints provided by the Unix operating system are several orders of magnitude too slow (and also several process switches too complicated) for the applications we have in mind. So we designed a breakpoint system that was fast enough for our purposes.Breakpoints for uni-processors running single threads of control used to be fast and simple to implement. This paper shows that breakpoints can still be fast, even with multiple threads of control on multi-processors. This paper describes problems in the design of a breakpoint package for modern computer architectures and programming styles, and our solutions to them for a particular architecture.
Soft typing
Authors: Cartwright Robert , Fagan Mike
Published: November 2005

Type systems are designed to prevent the improper use of program operations. They can be classified as either
static or dynamic
depending on when they detect type errors. Static type systems detect potential type errors at compile-time and
prevent
program execution. Dynamic type systems detect type errors at run-time and
abort
program execution.Static type systems have two important advantages over dynamic type systems. First, they help programmers detect a large class of program errors
before
execution. Second, they extract information that a compiler can exploit to produce more efficient code. The price paid for these advantages, however, is a loss of expressiveness, generality, and semantic simplicity.This paper presents a generalization of static and dynamic typing---called
soft typing
---that combines the best features of both approaches. The key idea underlying soft typing is that a static type checker need not
reject
programs that contain potential type errors. Instead, the type checker can insert explicit run-time checks around "suspect" arguments of primitive operations, converting dynamically typed programs into statically type-correct form. The inserted run-time checks identify program phrases that
may
be erroneous. For soft typing to be effective, the type system must avoid inserting unnecessary run-time checks. To accomplish this objective, we have developed an extension of the
ML
type system supporting union types and recursive types that assigns types to a wider class of programs than
ML
. We have also developed an algorithm for frugally inserting run-time checks in programs that do not type check.
A data locality optimizing algorithm
Authors: Lam Monica S. , Wolf Michael E.
Published: November 2005

This paper proposes an algorithm that improves the locality of a loop nest by transforming the code via interchange, reversal, skewing and tiling. The loop transformation algorithm is based on two concepts: a mathematical formulation of reuse and locality, and a loop transformation theory that unifies the various transforms as unimodular matrix transformations.The algorithm has been implemented in the SUIF (Stanford University Intermediate Format) compiler, and is successful in optimizing codes such as matrix multiplication, successive over-relaxation (SOR), LU decomposition without pivoting, and Givens QR factorization. Performance evaluation indicates that locality optimization is especially crucial for scaling up the performance of parallel code.
Lazy code motion
Authors: Knoop Jens , Rüthing Oliver , Steffen Bernhard
Published: November 2005

We present a bit-vector algorithm for the
optimal
and
economical
placement of computations within flow graphs, which is as
efficient
as standard uni-directional analyses. The point of our algorithm is the
decomposition
of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. Moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. This
laziness
of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.
The essence of compiling with continuations
Authors: Flanagan Cormac , Sabry Amr , Duba Bruce F. , Felleisen Matthias
Published: November 2005

In order to simplify the compilation process, many compilers for higher-order languages use the continuation-passing style (CPS) transformation in a first phase to generate an intermediate representation of the source program. The salient aspect of this intermediate form is that all procedures take an argument that represents the rest of the computation (the "continuation"). Since the naïve CPS transformation considerably increases the size of programs, CPS compilers perform reductions to produce a more compact intermediate representation. Although often implemented as a part of the CPS transformation, this step is conceptually a second phase. Finally, code generators for typical CPS compilers treat continuations specially in order to optimize the interpretation of continuation parameters.A thorough analysis of the abstract machine for CPS terms shows that the actions of the code generator
invert
the naïve CPS translation step. Put differently, the combined effect of the three phases is equivalent to a source-to-source transformation that simulates the compaction phase. Thus, fully developed CPS compilers do not need to employ the CPS transformation but can achieve the same results with a simple source-level transformation.
Complete removal of redundant expressions
Authors: Bodík Rastislav , Gupta Rajiv , Soffa Mary Lou
Published: November 2005

Partial redundancy elimination (PRE), the most important component of global optimizers, generalizes the removal of common subexpressions and loop-invariant computations. Because existing PRE implementations are based on
code motion
, they fail to completely remove the redundancies. In fact, we observed that 73% of loop-invariant statements cannot be eliminated from loops by code motion alone. In dynamic terms, traditional PRE eliminates only half of redundancies that are strictly partial. To achieve a
complete
PRE, control flow
restructuring
must be applied. However, the resulting code duplication may cause code size explosion.This paper focuses on achieving a complete PRE while incurring an acceptable code growth. First, we present an algorithm for
complete
removal of partial redundancies, based on the
integration
of code motion and control flow restructuring. In contrast to existing complete techniques, we resort to restructuring merely to remove obstacles to code motion, rather than to carry out the actual optimization.Guiding the optimization with a profile enables additional code growth reduction through selecting those duplications whose cost is justified by sufficient execution-time gains. The paper develops two methods for determining the optimization benefit of restructuring a program region, one based on path-profiles and the other on data-flow frequency analysis. Furthermore, the abstraction underlying the new PRE algorithm enables a simple formulation of speculative code motion guaranteed to have positive dynamic improvements. Finally, we show how to balance the three transformations (code motion, restructuring, and speculation) to achieve a near-complete PRE with very little code growth.We also present algorithms for efficiently computing dynamic benefits. In particular, using an elimination-style data-flow framework, we derive a demand-driven frequency analyzer whose cost can be controlled by permitting a bounded degree of conservative imprecision in the solution.
The design and implementation of a certifying compiler
Authors: Necula George C. , Lee Peter
Published: November 2005

This paper presents the design and implementation of a compiler that translates programs written in a type-safe subset of the C programming language into highly optimized DEC Alpha assembly language programs, and a
certifier
that automatically checks the type safety and memory safety of any assembly language program produced by the compiler. The result of the certifier is either a formal proof of type safety or a counterexample pointing to a potential violation of the type system by the target program. The ensemble of the compiler and the certifier is called a
certifying compiler.
Several advantages of certifying compilation over previous approaches can be claimed. The notion of a certifying compiler is significantly easier to employ than a formal compiler verification, in part because it is generally easier to verify the correctness of the result of a computation than to prove the correctness of the computation itself. Also, the approach can be applied even to highly optimizing compilers, as demonstrated by the fact that our compiler generates target code, for a range of realistic C programs, which is competitive with both the cc and gcc compilers with all optimizations enabled. The certifier also drastically improves the effectiveness of compiler testing because, for each test case, it statically signals compilation errors that might otherwise require many executions to detect. Finally, this approach is a practical way to produce the safety proofs for a Proof-Carrying Code system, and thus may be useful in a system for safe mobile code.
On bounding time and space for multiprocessor garbage collection
Authors: Blelloch Guy E. , Cheng Perry
Published: November 2005

Our paper described a real-time garbage collection algorithm for shared-memory multiprocessors. The work differed from previous work on multiprocessor garbage collection in that we were interested in placing hard bounds on pause times and memory usage. We felt this was important in justifying the term real-time, and for giving users a better handle on actual performance characteristics. Although the paper presented an algorithm without an implementation, and made some simplifying assumptions, we put considerable effort into making key aspects of the algorithm practical. In later work [9, 8] we implemented the ideas, and demonstrated performance characteristics that were in line with the characteristics predicted by the theory.This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying colector. We prove that the algorithm requires at most 2(
R
(1 + 2/
k
) +
N
+ 5
PD
) memory locations, where
P
is the number of processors,
R
is the maximum reachable space during a computation (number of locations accessible from the root set),
N
is the maximum number of reachable objects,
D
is the maximum depth of any data object, and
k
is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to
k
non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.
An empirical comparison of monitoring algorithms for access anomaly detection
Authors: Dinning A. , Schonberg E.
Published: November 2005

One of the major disadvantages of parallel programming with shared memory is the nondeterministic behavior caused by uncoordinated access to shared variables, known as
access anomalies
. Monitoring program execution to detect access anomalies is a promising and relatively unexplored approach to this problem. We present a new algorithm, referred to as
task recycling
, for detecting anomalies, and compare it to an existing algorithm. Empirical results indicate several significant conclusions: (i) While space requirements are bounded by Ο(
T
×
V
), where
T
is the maximum number of threads that may potentially execute in parallel and
V
is the number of variable monitored, for typical programs space requirements are on average Ο(
V
). (ii) Task recycling is more efficient in terms of space requirements and often in performance. (iii) The general approach of monitoring to detect access anomalies is practical.
A multi-level load balancing scheme for OR-parallel exhaustive search programs on the multi-PSI
Authors: Furuichi M. , Taki K. , Ichiyoshi N.
Published: November 2005

Good load balancing is the key to deriving maximal performance from multiprocessors. Several successful dynamic load balancing techniques on tightly-coupled multiprocessors have been developed. However, load balancing is more difficult on loosely-coupled multiprocessors because inter-processor communication overheads cost more. Dynamic load balancing techniques have been employed in a few programs on loosely-coupled multiprocessors, but they are tightly built into the particular programs and not much attention is paid to scalability. We have developed a dynamic load balancing scheme which is applicable to OR-parallel programs in general. Processors are grouped, and work loads of groups and processors are balanced hierarchically. Moreover, it is scalable to any number of processors because of this multi-level hierarchical structure. The scheme is tested for the all-solution exhaustive search Pentomino program on the mesh-connected loosely-coupled multiprocessor Multi-PSI, and speedups of 28.4 times with 32 processors and 50 times with 64 processors have been attained.
Real-time, concurrent checkpoint for parallel programs
Authors: Li K. , Naughton J. F. , Plank J. S.
Published: November 2005

We have developed and implemented a checkpointing and restart algorithm for parallel programs running on commercial uniprocessors and shared-memory multiprocessors. The algorithm runs concurrently with the target program, interrupts the target program for small, fixed amounts of time and is transparent to the checkpointed program and its compiler. The algorithm achieves its efficiency through a novel use of address translation hardware that allows the most time-consuming operations of the checkpoint to be overlapped with the running of the program being checkpointed.
A Chare kernel implementation of a parallel Prolog compiler
Authors: Ramkumar B. , Kale L. V.
Published: November 2005

We have designed and implemented a compiler for the parallel execution of Prolog programs as a
machine independent
application on top of a run time environment for parallel programming called the
Chare Kernel
. The compiler is based on the Reduce-OR process model for the AND and OR parallel execution of Prolog programs and hence exploits both OR and independent AND parallelism found in Prolog programs. We describe the salient features of the parallel Prolog compiler from the viewpoint of its implementation as a
Chare Kernel
application. The responsibilities of process creation, load balancing, queueing strategies for
work pool
management, memory management and interprocess communication are all assumed by the
Chare Kernel
thereby eliminating these concerns at the application level. We discuss the effectiveness of this separation for a large application like the parallel Prolog compiler. The machine independence property makes the compiler easy to port on all machines, both shared and nonshared, that support the
Chare Kernel
. The compiler has been implemented on a variety of machines, including the Encore Multimax, the Sequent Symmetry, the Intel iPSC/2 hypercube and the Alliant FX/8. We briefly discuss its performance on a range of benchmarks exhibiting AND, OR and AND/OR parallelism on two of these machines. The speedups obtained are linear, demonstrating the effectiveness of the
Chare Kernel
as a simple, elegant, yet powerful environment for parallel programming.
The process trellis architecture for real-time monitors
Authors: Factor M.
Published: November 2005

The process trellis is a parallel software architecture for building heuristic real-time monitors. These programs, for example Intelligent Cardiovascular Monitors, must process massive quantities of data in real time. It is natural to turn to parallelism to meet these computational requirements. The process trellis software architecture is intended to simplify the creation and maintenance of heuristic real-time monitors. To do this it must be 1) modular, 2) efficient and 3) predictable.

This paper presents the goals and an overview of the process trellis. We have implemented a process trellis shell, which we describe. It is in use as the frame for an Intelligent Cardiovascular Monitor (ICM) which we are building with colleagues from the Yale School of Medicine. An analytical model is able to produce an upper bound on the time required by arbitrary trellis programs. Finally, we report on the predicted and actual performance of the ICM and synthetic programs consisting of roughly 7000 processes.
Verifying safety properties using separation and heterogeneous abstractions
Authors: Yahav Eran , Ramalingam G.
Published: November 2005

In this paper, we show how
separation
(decomposing a verification problem into a collection of verification subproblems) can be used to improve the efficiency and precision of verification of safety properties. We present a simple language for specifying
separation strategies
for decomposing a single verification problem into a set of subproblems. (The strategy specification is distinct from the safety property specification and is specified separately.) We present a general framework of
heterogeneous abstraction
that allows different parts of the heap to be abstracted using different degrees of precision at different points during the analysis. We show how the goals of separation (i.e., more efficient verification) can be realized by first using a separation strategy to transform (instrument) a verification problem instance (consisting of a safety property specification and an input program), and by then utilizing heterogeneous abstraction during the verification of the transformed verification problem.
A cost-driven compilation framework for speculative parallelization of sequential programs
Authors: Du Zhao-Hui , Lim Chu-Cheow , Li Xiao-Feng , Yang Chen , Zhao Qingyu , Ngai Tin-Fook
Published: November 2005

The emerging hardware support for thread-level speculation opens new opportunities to parallelize sequential programs beyond the traditional limits. By speculating that many data dependences are unlikely during runtime, consecutive iterations of a sequential loop can be executed speculatively in parallel. Runtime parallelism is obtained when the speculation is correct. To take full advantage of this new execution model, a program needs to be programmed or compiled in such a way that it exhibits high degree of speculative thread-level parallelism. We propose a comprehensive cost-driven compilation framework to perform speculative parallelization. Based on a misspeculation cost model, the compiler aggressively transforms loops into optimal speculative parallel loops and selects only those loops whose speculative parallel execution is likely to improve program performance. The framework also supports and uses enabling techniques such as loop unrolling, software value prediction and dependence profiling to expose more speculative parallelism. The proposed framework was implemented on the ORC compiler. Our evaluation showed that the cost-driven speculative parallelization was effective. Our compiler was able to generate good speculative parallel loops in ten Spec2000Int benchmarks, which currently achieve an average 8% speedup. We anticipate an average 15.6% speedup when all enabling techniques are in place.
Symbolic pointer analysis revisited
Authors: Zhu Jianwen , Calman Silvian
Published: November 2005

Pointer analysis is a critical problem in optimizing compiler, parallelizing compiler, software engineering and most recently, hardware synthesis. While recent efforts have suggested symbolic method, which uses Bryant's Binary Decision Diagram as an alternative to capture the point-to relation, no speed advantage has been demonstrated for context-insensitive analysis, and results for context-sensitive analysis are only preliminary.In this paper, we refine the concept of symbolic transfer function proposed earlier and establish a common framework for both context-insensitive and context-sensitive pointer analysis. With this framework, our transfer function of a procedure can abstract away the impact of its callers and callees, and represent its point-to information completely, compactly and canonically. In addition, we propose a symbolic representation of the invocation graph, which can otherwise be exponentially large. In contrast to the classical frameworks where context-sensitive point-to information of a procedure has to be obtained by the application of its transfer function exponentially many times, our method can obtain point-to information of all contexts in a single application. Our experimental evaluation on a wide range of C benchmarks indicates that our context-sensitive pointer analysis can be made almost as fast as its context-insensitive counterpart.
Jedd
Authors: Lhoták Ondřej , Hendren Laurie
Published: November 2005

In this paper we present Jedd, a language extension to Java that supports a convenient way of programming with Binary Decision Diagrams (BDDs). The Jedd language abstracts BDDs as database-style relations and operations on relations, and provides static type rules to ensure that relational operations are used correctly.The paper provides a description of the Jedd language and reports on the design and implementation of the Jedd translator and associated runtime system. Of particular interest is the approach to assigning attributes from the high-level relations to physical domains in the underlying BDDs, which is done by expressing the constraints as a SAT problem and using a modern SAT solver to compute the solution. Further, a runtime system is defined that handles memory management issues and supports a browsable profiling tool for tuning the key BDD operations.The motivation for designing Jedd was to support the development of whole program analyses based on BDDs, and we have used Jedd to express five key interrelated whole program analyses in our Soot compiler framework. We provide some examples of this application and discuss our experiences using Jedd.
Parametric regular path queries
Authors: Liu Yanhong A. , Rothamel Tom , Yu Fuxiang , Stoller Scott D. , Hu Nanjun
Published: November 2005

Regular path queries are a way of declaratively expressing queries on graphs as regular-expression-like patterns that are matched against paths in the graph. There are two kinds of queries: existential queries, which specify properties about individual paths, and universal queries, which specify properties about all paths. They provide a simple and convenient framework for expressing program analyses as queries on graph representations of programs, for expressing verification (model-checking) problems as queries on transition systems, for querying semi-structured data, etc. Parametric regular path queries extend the patterns with variables, called parameters, which significantly increase the expressiveness by allowing additional information along single or multiple paths to be captured and relate.This paper shows how a variety of program analysis and model-checking problems can be expressed easily and succinctly using parametric regular path queries. The paper describes the specification, design, analysis, and implementation of algorithms and data structures for efficiently solving existential and universal parametric regular path queries. Major contributions include the first complete algorithms and data structures for directly and efficiently solving existential and universal parametric regular path queries, detailed complexity analysis of the algorithms, detailed analytical and experimental performance comparison of variations of the algorithms and data structures, and investigation of efficiency tradeoffs between different formulations of queries.
Precise and efficient static array bound checking for large embedded C programs
Authors: Venet Arnaud , Brat Guillaume
Published: November 2005

In this paper we describe the design and implementation of a static array-bound checker for a family of embedded programs: the flight control software of recent Mars missions. These codes are large (up to 280 KLOC), pointer intensive, heavily multithreaded and written in an object-oriented style, which makes their analysis very challenging. We designed a tool called C Global Surveyor (CGS) that can analyze the largest code in a couple of hours with a precision of 80%. The scalability and precision of the analyzer are achieved by using an incremental framework in which a pointer analysis and a numerical analysis of array indices mutually refine each other. CGS has been designed so that it can distribute the analysis over several processors in a cluster of machines. To the best of our knowledge this is the first distributed implementation of static analysis algorithms. Throughout the paper we will discuss the scalability setbacks that we encountered during the construction of the tool and their impact on the initial design decisions.
Region inference for an object-oriented language
Authors: Chin Wei-Ngan , Craciun Florin , Qin Shengchao , Rinard Martin
Published: November 2005

Region-based memory management offers several important potential advantages over garbage collection, including real-time performance, better data locality, and more efficient use of limited memory. Researchers have advocated the use of regions for functional, imperative, and object-oriented languages. Lexically scoped regions are now a core feature of the Real-Time Specification for Java (RTSJ)[5].Recent research in region-based programming for Java has focused on region checking, which requires manual effort to augment the program with region annotations. In this paper, we propose an automatic region inference system for a core subset of Java. To provide an inference method that is both precise and practical, we support classes and methods that are region-polymorphic, with region-polymorphic recursion for methods. One challenging aspect is to ensure region safety in the presence of features such as class subtyping, method overriding, and downcast operations. Our region inference rules can handle these object-oriented features safely without creating dangling references.
A universal intermediate representation for massively parallel software development
Authors: Wells Paul Damian
Published: November 2005

The Hierarchical Simultaneous Set Membership (HSSM) intermediate representation is a graphical representation that can be used to efficiently encode source languages during parsing. It also provides an excellent design representation for code generation as well. Moreover, the HSSM IR is the basis for a
relational algebra
. Where a relational algebra is to software design what Boolean algebra is to digital logic design. This formal mathematical interpretation makes the HSSM IR an excellent platform on which to develop the extensive automated synthesis/verification algorithms that will necessarily form the basis of next generation computers.
Lexical analysis tool
Authors: Kantorovitz Isaiah Pinchas
Published: November 2005

This paper provides an algorithm for constructing a lexical analysis tool, by different means than the UNIX Lex tool. The input is a keywords table, describing the target language's keywords, keysymbols, and their semantics, instead of using regular expressions to do so.The output is a lexical analyzer for the specific programming language. The tool can also be used as a translator engine by inputing a dictionary table, and as a pattern recognizer.
Modeling and simulating electronic textile applications
Authors: Martin Thomas , Jones Mark , Edmison Joshua , Sheikh Tanwir , Nakad Zahi
Published: November 2005

This paper describes our design of a simulation environment for electronic textiles (e-textiles) and our experiences with that environment. This simulation environment, based upon Ptolemy II, enables us to model a diverse range of areas related to the design of electronic textiles, including the physical environment they will be used in, the behavior of the sensors incorporated into the fabric, the on-fabric network, the power consumption of the system, and the execution of the application and system software. This paper focuses on two aspects of the system, modeling the motion of a person wearing the e-textile and modeling the effect of faults in the e-textile system. To partially validate this environment, we compare simulation results against results from two different physical prototypes, a large-scale acoustic beamformer and a pair of shape-sensing pants.
Spinach
Authors: Willmann Paul , Brogioli Michael , Pai Vijay S.
Published: November 2005

This paper presents Spinach, a new simulator toolset specifically designed to target programmable network interface architectures. Spinach models both system components that are common to all programmable environments (e.g., ALUs, control and data paths, registers, instruction processing) and components that are specific to the embedded systems and network interface environments (e.g., software-controlled scratchpad memory, hardware assists for DMA and medium access control).Spinach is built on the Liberty Simulation Environment (LSE) and exploits LSE's modularity to support easy reconfiguration of programmable network interface cards (NICs) and embedded systems, enabling wide design space exploration with little or no code variation. For example, the same underlying C code is used whether supporting a uniprocessor Gigabit network interface, a multiprocessor Gigabit interface, or a multiprocessor 10 Gigabit interface with a highly heterogeneous memory system. The only difference is in a small number of lines of high-level scripting code used to configure the various modules into a simulation model.Spinach is validated by modeling the Tigon-2 programmable Ethernet controller by Alteon Websystems running actual Ethernet processing firmware and by comparing the reported results to actual hardware benchmarks. Spinach is then used to obtain new insights about the performance of Gigabit and 10 Gigabit network interfaces.
NDL
Authors: Conway Christopher L. , Edwards Stephen A.
Published: November 2005

Device drivers are difficult to write and error-prone. They are usually written in C, a fairly low-level language with minimal type safety and little support for device semantics. As a result, they have become a major source of instability in operating system code.This paper presents NDL, a language for device drivers. NDL provides high-level abstractions of device resources and constructs tailored to describing common device driver operations. We show that NDL allows for the coding of a semantically correct driver with a code size reduction of more than 50% and a minimal impact on performance.
Asynchronous software thread integration for efficient software
Authors: Kumar Nagendra J. , Shivshankar Siddhartha , Dean Alexander G.
Published: November 2005

The overhead of context-switching limits efficient scheduling of multiple concurrent threads on a uniprocessor when real-time requirements exist. Existing software thread integration (STI) methods reduce context switches, but only provide synchronous thread progress within integrated functions. For the remaining, non-integrated portions of the secondary threads to run and avoid starvation, the primary thread must have adequate amounts of coarse-grain idle time (longer than two context-switches). We have developed
asynchronous
software thread integration (ASTI) methods which address starvation through the efficient use of coroutine calls and integration. ASTI allows threads to make independent progress efficiently and reduces the number of context switches needed through integration.Software-implemented protocol controllers are crippled by this problem; the primary thread "bit-bangs" each bit of a message onto or off of the bus, leaving only fragments of idle time shorter than a bit time. This fragmented time may be too short to recover through context switching, so only the primary thread can execute during message transmission or reception, slowing the secondary threads and potentially making them miss their deadlines. ASTI simplifies the implementation of embedded communication protocols on low-cost, moderate speed (1 - 100 MHz, 8- and 16-bit) microcontrollers. We demonstrate ASTI by replacing a standard automotive communication protocol controller (J1850) with software and generic hardware. Secondary thread performance improves significantly when compared with a traditional interrupt-based software approach.
A formal concurrency model based architecture description language for synthesis of software development tools
Authors: Qin Wei , Rajagopalan Subramanian , Malik Sharad
Published: November 2005

Rapidly increasing design and manufacturing non-recurring engineering (NRE) costs are prompting a shift in electronic design from hardwired application specific integrated circuits (ASICs) to the use of software on programmable platforms. However, in order to minimize the power and performance overhead of such processors, we are seeing the introduction of domain or application specific processors such as network and communication processors. The design of such specialized processors requires software development tools such as simulators and compilers. In order to quickly develop these tools for multiple design points under consideration, it is highly desirable to have them synthesized from formal processor descriptions written in Architecture Description Languages (ADLs). In this paper, we present the Mescal Architecture Description Language (MADL). MADL features a two-layer structure, a core layer and an annotation layer. The core layer is based on a formal and flexible microprocessor model -- the operation state machine (OSM), which enables MADL to express the concurrency at the operation execution level for a wide range of architectures. We address the challenges faced in designing the core layer to combine the OSM model with techniques for achieving compact processor descriptions. The annotation layer features a generic syntax that allows creating annotation schemes to specify implementation dependent or tool specific information. To show the effectiveness of MADL, we present an MADL-based simulator synthesis framework that has been used to generate efficient cycle accurate simulators and instruction set simulators with very low development effort. We also describe our annotation schemes that enable the extraction of architecture properties for use in instruction scheduling and integer-linear-programming based register allocation. Our experimental results demonstrate the efficacy of MADL as a practical and promising language for the development of programmable platforms.
Procrastination scheduling in fixed priority real-time systems
Authors: Jejurikar Ravindra , Gupta Rajesh
Published: November 2005

Procrastination scheduling has gained importance for energy efficiency due to the rapid increase in the leakage power consumption. Under procrastination scheduling, task executions are delayed to extend processor shutdown intervals, thereby reducing the idle energy consumption. We propose algorithms to compute the maximum procrastination intervals for tasks scheduled by either the fixed priority or the dual priority scheduling policy. We show that dual priority scheduling always guarantees longer shutdown intervals than fixed priority scheduling. We further combine procrastination scheduling with dynamic voltage scaling to minimize the total static and dynamic energy consumption of the system. Our simulation experiments show that the proposed algorithms can extend the sleep intervals up to 5 times while meeting the timing requirements. The results show up to 18% energy gains over dynamic voltage scaling.
Power-efficient prefetching via bit-differential offset assignment on embedded processors
Authors: Zhuang Xiaotong , Pande Santosh
Published: November 2005

Due to stringent power constraints, aggressive latency hiding approaches such as prefetching are absent in the state-of-the-art embedded processors. There are two main reasons that cause prefetching to be power inefficient. First, compiler inserted prefetch instructions increase code size, therefore could increase I-cache power. Secondly, inaccurate prefetching (esp. for hardware prefetching) leads to high D-cache power consumption due to the useless accesses. In this work, we show that it is possible to support power-efficient prefetching through bit-differentail offset assignment to stack variables.We target the prefetching of relocatable stack variables with a high degree of precision. By assigning the offsets of stack variables in such a way that most consecutive addresses differ by 1 bit, we can prefetch them with compact prefetch instructions to save I-cache power. The compiler first generates an access graph of consecutive memory references and then attempts a layout of the memory locations in the smallest hypercube. Each dimension of the hypercube represents a 1-bit differential addressing. The embedding is carried out in as compact a hypercube as possible in order to save memory space. Each load/store instruction carries a hint regarding prefetching the next memory reference by encoding its differential address with respect to the current one. To reduce D-cache power cost, we further attempt to assign offsets so that most of the consecutive accesses map to the same cache line. Our prefetching is done using a one entry line buffer[1]. As a consequence, many look-ups in D-cache reduce to incremental ones. This results in D-cache activity reduction and power savings.Our prefetching requires both compiler and hardware support. In this paper, we provide implementation on the ARM processor with small modification to the ARM ISA. We tackle issues about out of order commit, predication and speculation through simple modifications to the processor pipeline on non-critical paths. Our goal in this work is to boost performance while maintaining/lowering power consumption. Our results show 12% speed-up and slightly lower power consumption.
Speculative software management of datapath-width for energy optimization
Authors: Pokam Gilles , Rochecouste Olivier , Seznec André , Bodin François
Published: November 2005

This paper evaluates managing the processor's datapath-width at the compiler level by means of exploiting dynamic narrow-width operands. We capitalize on the large occurrence of these operands in multimedia programs to build static narrow-width regions that may be directly exposed to the compiler. We propose to augment the ISA with instructions directly exposing the datapath and the register widths to the compiler. Simple exception management allows this exposition to be only speculative. In this way, we permit the software to speculatively accommodate the execution of a program on a narrower datapath-width in order to save energy. For this purpose, we introduce a novel register file organization, the
byte-slice
register file, which allows the width of the register file to be dynamically reconfigured, providing both static and dynamic energy savings. We show that by combining the advantages of the
byte-slice
register file with the advantages provided by clock-gating the datapath on a per-region basis, up to 17% of the datapath dynamic energy can be saved, while a 22% reduction of the register file static energy is achieved.
Dynamic voltage scaling for real-time multi-task scheduling using buffers
Authors: Im Chaeseok , Ha Soonhoi
Published: November 2005

This paper proposes energy efficient real-time multi-task scheduling (EDF and RM) algorithms by using buffers. The buffering technique overcomes a drawback of previous approaches by utilizing the slack time of a system fully. It increases the CPU utilization and averages the workload of a system, so it enhances the effectiveness of the DVS technique. We target multimedia applications where a slight buffering delay is tolerable within a latency constraint. We modify the state transition and queue handling mechanism of multi-task scheduling in the kernel. In experiments, our algorithms achieve up to 44% of energy consumption saving for EDF scheduling and 49% for RM scheduling with realistic task set configurations and reasonable machine specifications.