Loading...
Please wait, while we are loading the content...
Similar Documents
Partitioning Non-strict Functional Languages for Partitioning Non-strict Functional Languages for Multi-threaded Code
| Content Provider | Semantic Scholar |
|---|---|
| Author | Coorg, Satyan R. |
| Copyright Year | 1995 |
| Abstract | In this paper, we present a new approach to partitioning, the problem of generating sequential threads for programs written in a non-strict functional language. The goal of partitioning is to generate threads as large as possible, while retaining the non-strict semantics of the program. We deene partitioning as a program transformation and design algorithms for basic block partitioning and inter-procedural partitioning. The inter-procedural algorithm presented here is more powerful than the ones previously known and is based on abstract interpretation, enabling the algorithm to handle recursion in a straightforward manner. We prove the correctness of these algorithms in a denotational semantic framework. and tolerance sets, inter-procedural analysis, non-strict functional languages. 1 Introduction Functional programming languages can be divided into two classes: strict and non-strict. In a non-strict language, functions may return values before all their arguments are available , and data structures may be deened before all their components are deened. Many modern functional languages are non-strict; examples include Haskell 13] and Id 17]. Such languages give greater expressive power to the programmer than a strict language. Some of the languages provide non-strictness because of its cleaner semantics. Others, like Id, also use non-strictness to generate parallelism in a program. Compiling non-strict languages to conventional microprocessors has been the focus of many recent papers 26, 21, 20]. Some features in the design of commercial microprocessors make it diicult to execute non-strict programs directly. These processors are highly tuned to execute a sequence of instructions eeciently by providing features like a large register set and deep pipelining. Unfortunately, this also implies that there is a high penalty for dynamic scheduling of instructions. As serial execution is interrupted, registers have to be saved and restored, there may be bubbles in the instruction pipeline etc. Synchronization is also expensive |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-378.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
