6734680
Compiler Optimizations for Adaptive EPIC Processors
Advances in VLSI technology have lead to a tremendous increase in the density and number of devices that can be manufactured in a single microchip. One of the interesting ways in which this silicon may be used is to leave portions of it uncommitted and re-programmable depending on an applications needs. In an earlier paper, we proposed a machine architecture for achieving this reconfigurability and compilation issues that such an architecture will face. In this paper, we will elaborate on the compiler optimization issues involved. In particular, we will outline a framework for code partitioning, instruction synthesis, configuration selection, resource allocation, and instruction scheduling. Partitioning is the problem of identifying code sections that may benefit by mapping them on to the programmable logic resources. The instruction synthesis phase generates suitable implementations for the candidates partitions and updates the machine description database with the new instructions. Configuration selection is the problem of narrowing down the choices of which synthesized instruction (from the set generated by the instruction synthesis phase) to use for each of the code regions that will be mapped to programmable logic. Unlike traditional optimizing compilers, the adaptive EPIC compiler must deal with the existence of synthesized instructions. Compilation techniques addressing each of these problems will be presented.
18143878
Compiling Parallel Lisp for a Shared Memory Multiprocessor
There is a commonly held idea that although Lisp is a good language for prototyping and software development, it is often too inefcient to be useful in actual implementation. Advances in compiling Lisp have begun to change this notion. However, the situation is less clear in the case of parallel Lisp dialects. In this paper, we report on our experience in implementing a compiler for a parallel Lisp dialect we called BaLinda Lisp for a shared memory multiprocessor. For a class of problems, our compiler was able to achieve performances on Lisp programs that are near, if not equal to, their imperative (C) equivalents. However, on other problems, the situation is less than ideal. We investigate this phenomenum and outline the future challenges in realizing a production strength parallel Lisp compiler.
3467496
Compiler orchestrated prefetching via speculation and predication
This paper introduces a compiler orchestrated prefetching system as a unified framework geared toward ameliorating the gap between processing speeds and memory access latencies. We focus the scope of the optimization on specific subsets of the program dependence graph that succinctly characterize the memory access pattern of both regular array-based applications and irregular pointer-intensive programs. We illustrate how program embedded precomputation via speculative execution can accurately predict and effectively prefetch future memory references with negligible overhead. The proposed techniques reduce the total running time of seven SPEC benchmarks and two OLDEN benchmarks by 27% on an Itanium 2 processor. The improvements are in addition to several state-of-the-art optimizations including software pipelining and data prefetching. In addition, we use cycle-accurate simulations to identify important and lightweight architectural innovations that further mitigate the memory system bottleneck. In particular, we focus on the notoriously challenging class of pointer-chasing applications, and demonstrate how they may benefit from a novel scheme of it sentineled prefetching. Our results for twelve SPEC benchmarks demonstrate that 45% of the processor stalls that are caused by the memory system are avoidable. The techniques in this paper can effectively mask long memory latencies with little instruction overhead, and can readily contribute to the performance of processors today.
5375170
Fast evaluation of the elementary functions in double precision
One of the most spectacular development in computer technology is the growth in memory density and speed. It is with this development in mind that we intend to tackle the old problem of computing the elementary functions. Since the dawn of computing, the fast and accurate computation of the elementary functions has been a constant concern of numerical computing. It now seems possible to use tables of sizes in the range of megabits to aid in such computation. To this end, in this paper, we propose a method called ATA-M (Add-Table Lookup-Add with Multiplication) for evaluating polynomials with the aid of tables. When applied to the elementary functions, we obtained a set of algorithms which computes the reciprocal, square root, exponential, sine, cosine, logarithm, are tangent and the hyperbolic functions in about 3 to 4 double precision floating point multiplication time and utilizing about 2 Mbyte of tables.<<ETX>>
3457072
Using UML 2.0 for system level design of real time SoC platforms for stream processing
While enabling fast implementation and reconfiguration of stream applications, programmable stream processors expose issues of incompatibility and lack of adoption in existing stream modeling languages. To address them we describe a design approach in which specifications are captured in UML 2.0, and automatically translated into SystemC models consisting of simulators and synthesizable code under proper style constraints. As an application case, we explain real time stream processor specifications using new UML 2.0 notations. Then we expound how our translator generates SystemC models and includes additional hardware details. Verifications are made during UML execution as well as assertions in SystemC. The case study demonstrates the feasibility of fast specifications, modifications and generation of real time stream processor designs.
1841047
Design and Implementation of Abstract Machine for Parallel Lisp Compilation
22795499
GeneNotes – A novel information management software for biologists
BackgroundCollecting and managing information is a challenging task in a genome-wide profiling research project. Most databases and online computational tools require a direct human involvement. Information and computational results are presented in various multimedia formats (e.g., text, image, PDF, word files, etc.), many of which cannot be automatically processed by computers in biologically meaningful ways. In addition, the quality of computational results is far from perfect and requires nontrivial manual examination. The timely selection, integration and interpretation of heterogeneous biological information still heavily rely on the sensibility of biologists. Biologists often feel overwhelmed by the huge amount of and the great diversity of distributed heterogeneous biological information.DescriptionWe developed an information management application called GeneNotes. GeneNotes is the first application that allows users to collect and manage multimedia biological information about genes/ESTs. GeneNotes provides an integrated environment for users to surf the Internet, collect notes for genes/ESTs, and retrieve notes. GeneNotes is supported by a server that integrates gene annotations from many major databases (e.g., HGNC, MGI, etc.). GeneNotes uses the integrated gene annotations to (a) identify genes given various types of gene IDs (e.g., RefSeq ID, GenBank ID, etc.), and (b) provide quick views of genes. GeneNotes is free for academic usage. The program and the tutorials are available at: http://bayes.fas.harvard.edu/genenotes/.ConclusionsGeneNotes provides a novel human-computer interface to assist researchers to collect and manage biological information. It also provides a platform for studying how users behave when they manipulate biological information. The results of such study can lead to innovation of more intelligent human-computer interfaces that greatly shorten the cycle of biology research.
7989519
Local Disk Depot - Customizing the Software Environment
The depot model, developed at Carnegie Mellon University, provides a method for managing third-party and locally developed software. depot uses an object-oriented approach to managing software; each software package is managed as one or more logical objects. Yet, from the perspective of a user, the multiple ‘‘software objects’’ appear as a single, integrated, software environment. Local disk depot (ldd) is an extension to the depot framework. ldd facilitates the management of environments that ‘‘inherit’’ software from the ‘‘master’’ software environments. The inherited software environment is formed by taking software and configuration information from the master software environments, and integrating that with local software and configuration information. The most common use of ldd is to have an inherited environment on the local disk of a workstation. This allows the workstation administrator to locally cache software in order to improve performance and availability of critical software in the event of server or network failure. The inherited environments, however, can be used for more than saving local copies of remote software. Workstation administrators can introduce customizations to the software environment, as well as add additional software, even from other software environments. Developers can easily test new or updated applications on their own machines in an environment that is otherwise identical to the released environment.
15561139
A case study of the recursive least squares estimation approach to adaptive testing for software components
The strategy used for testing a software system should not be fixed, because as time goes on we may have a better understanding of the software under test. A solution to this problem is to introduce control theory into software testing. We can use adaptive testing where the testing strategy is adjusted on-line by using the data collected during testing. Since the use of software components in software development is increasing, it is now more important than ever to adopt a good strategy for testing software components. In this paper, we use an adaptive testing strategy for testing software components. This strategy (AT/spl I.bar/RLSE/sub c/ with c indicating components) applies a recursive least squares estimation (RLSE) method to estimate parameters such as failure detection rate. It is different from the genetic algorithm-based adaptive testing (AT/spl I.bar/GA) where a genetic algorithm is used for parameter estimation. Experimental data from our case study suggest that the fault detection effectiveness of AT/spl I.bar/RLSE/sub c/ is better than that of AT/spl I.bar/GA and random testing.
11803699
An agent-based testing approach for Web applications
In recent years, Web applications have grown so quickly that they have already become crucial to the success of businesses. However, since they are built on Internet and open standard technologies, Web applications bring new challenges to researchers, such as dynamic behaviors, heterogeneous representations, novel control flow and data flow mechanisms, etc. In this paper, we propose an agent-based approach for Web application testing. While the agent-based framework greatly reduces the complexity of Web applications, a four-level dataflow test approach can be employed to perform structure testing on them. In this approach, data flow analysis is performed as function level testing, function cluster level testing, object level testing, and Web application level testing, from low abstract level to high abstract level. Each test agent in the framework takes charge of the testing in an abstract level for a particular type of Web document or object.
17907717
Effective generation of test sequences for structural testing of concurrent programs
One common approach to test sequence generation for structurally testing concurrent programs involves constructing a reachability graph (RG) and selecting a set of paths from the graph to satisfy some coverage criterion. It is often suggested that test sequence generation methods for testing sequential programs based on a control flow graph (CFG) can also be used to select paths from a RG for testing concurrent programs. However, there is a major difference between these two, as the former suffers from a feasibility problem (i.e., some paths in a CFG may not be feasible at run-time) and the latter does not. As a result, even though test sequence generation methods for sequential programs can be applied to concurrent programs, they may not be efficient. Moreover, in order to reduce testing effort and costs, it is important to reduce the number of test sequences being generated. Stated differently, we need methods which can generate efficient test sequences to increase the coverage in an effective way. We propose four different methods - two based on hot spot prioritization and two based on topological sort -to effectively generate a small set of test sequences that cover all the nodes in a RG. The same methods are also applied to the corresponding dual graph for generating test sequences to cover all the edges. A case study was conducted to demonstrate the use of our methods.