1,721,052 research outputs found
Publication Notes
No full textThis work may not be copied or reproduced in whole or in part for any commercial purpose. Permission to copy in whole or in part without payment of fee is granted for non-profit educational and research purposes provided that all such whole or partial copies include the following: a notice that such copying is by permission of the Paris Research Laboratory of Digital Equipment Centre Technique Europe, in Rueil-Malmaison, France; an acknowledgement of the authors and individual contributors to the work; and all applicable portions of the copyright notice. Copying, reproducing, or republishing for any other purpose shall require a license with payment of fee to the Paris Research Laboratory. All rights reserved. ii This note outlines the Life Abstract Machine (LAM), an abstract machine used as an intermediate target for the efficient compilation of LIFE. LAM focuses primarily on the efficient implementation of matching, residuation, and currying of functions. Although the topic is not discussed in this note, LAM also implements lazy unification. LAM should be viewed as an intermediate target for compiling LIFE to a native instruction set for a general purpose processor. Thus, this note presents LAM as an abstract machine along with its instructions. However, we also discuss how LAM would be realized in terms of data structures and basic routines. This should facilitate the implementation of both a LIFE-to-LAM compiler and a LAM-to-native-code compiler. iii Keyword
The Challenges and Opportunities of Nanoelectronics
No full textNanoelectronics presents the opportunity of incorporating billions of devices into a single system. Its opportunity is also its challenge: the economic design, verification, manufacturing, and testing of billion component systems. In this presentation I will explore how the abstractions used in computer systems change as we approach nanoscale dimensions
Lazy Threads: Compiler and Runtime Structures for Fine-Grained Parallel Programming
No full textMany modern parallel languages support dynamic creation of threads or require multithreading in their implementations. The threads describe the logical parallelism in the program. For ease of expression and better resource utilization, the logical parallelism in a program often exceeds the physical parallelism of the machine and leads to applications with many fine-grained threads. In practice, however, most logical threads need not be independent threads. Instead, they could be run as sequential calls, which are inherently cheaper than independent threads. The challenge is that one cannot generally predict which logical threads can be implemented as sequential calls. In lazy multithreading systems each logical thread begins execution sequentially (with the attendant effic..
Fast Compilation for Pipelined Reconfigurable Fabrics
No full textIn this paper we describe a compiler which quickly synthesizes high quality pipelined datapaths for pipelined reconfigurable devices. The compiler uses the same internal representation to perform synthesis, module generation, optimization, and place and route. The core of the compiler is a linear time place and route algorithm more than two orders of magnitude faster than traditional CAD tools. The key behind our approach is that we never backtrack, rip-up, or re-route. Instead, the graph representing the computation is preprocessed to guarantee routability by inserting lazy noops. The preprocessing steps provides enough information to make a greedy strategy feasible. The compilation speed is approximately 3000 bit-operations/second (on a PII/400Mhz) for a wide range of applications. The hardware utilization averages 60% on the target device, PipeRench. 1 Introduction Reconfigurable computing has the potential to change the way computing is performed. Such systems offer a many-fold in..
Detecting and Exploiting Narrow Bitwidth Computations
No full textMany important applications perform computations on non-standard bit-width values; mapping them to word-based processing units is wasteful of resources and results in suboptimal performance. While there are some processor architecture innovations which take advantage of varying bit-widths, compiler optimizations lag far behind. We present a compiler algorithm which infers minimal widths and constant bits using several program analyses. We present forward analyses, which compute the signs, find bits independent of the inputs and find constant bits; we describe a backward analysis, which discovers bits unused by the output; we also describe a mixing analysis, which trims all unnecessary work from the computation, by using the results of the other analyses. We show how these techniques can be used in a compiler for reconfigurable hardware to achieve substantial reductions in the size of the synthesized circuits (up to 20 times). We also show how the algorithm can be used to anal..
A Progressive Register Allocator for Irregular Architectures
No full text... a compiler performs. Conventional graph-coloring based register allocators are fast and do well on regular, RISC-like, architectures, but perform poorly on irregular, CISC-like, architectures with few registers and nonorthogonal instruction sets. At the other extreme, optimal register allocators based on integer linear programming are capable of fully modeling and exploiting the peculiarities of irregular architectures but do not scale well. We introduce the idea of a progressive allocator. A progressive allocator finds an initial allocation of quality comparable to a conventional allocator, but as more time is allowed for computation the quality of the allocation approaches optimal. This paper presents a progressive register allocator which uses a multi-commodity network flow model to elegantly represent the intricacies of irregular architectures. We evaluate our allocator as a substitute for gcc's local register allocation pass
Why area might reduce power in nanoscale CMOS
No full textAbstract — In this paper we explore the relationship between power and area. By exploiting parallelism (and thus using more area) one can reduce the switching frequency allowing a reduction in VDD which results in a reduction in power. Under a scaling regime which allows threshold voltage to increase as VDD decreases we find that dynamic and subthreshold power loss in CMOS exhibit a dependence on area proportional to A(σ−3)/σ while gate leakage power ∝ A(σ−6)/σ and short circuit power ∝ A(σ−8)/σ. Thus, with the large number of devices at our disposal we can exploit techniques such as spatial computing–tailoring the program directly to the hardware–to overcome the negative effects of scaling. The value of σ describes the effectiveness of the technique for a particular circuit and/or algorithm–for circuits that exhibit a value of σ ≤3, power will be a constant or reducing function of area. We briefly speculate on how σ might be influenced by a move to nanoscale technology. I
- …
