Change search
ReferencesLink to record
Permanent link

Direct link
Formal derivation of concurrent assignments from scheduled single assignments
Number of Authors: 1
1991 (English)Report (Refereed)
Abstract [en]

Concurrent assignments are commonly used to describe synchronous parallel computations. We show how a sequence of concurrent assignments can be formally derived from the schedule of an acyclic single assignment task graph and a memory allocation. In order to do this we develop a formal model of memory allocation in synchronous systems. We use weakest precondition semantics to show that the sequence of concurrent assignments computes the same values as the scheduled single assignments. We give a lower bound on the memory requirements of memory allocations for a given schedule. This bound is tight: we define a class of memory allocations whose memory requirements always meets the bound. This class corresponds to conventional register allocation for DAGs and is suitable when memory access times are uniform. We furthermore define a class of simple ``shift register'' memory allocation. These allocations have the advantage of a minimum of explicit storage control and they yield local or nearest-neighbour accesses in distributed systems whenever the schedule allows this. Thus, this class of allocations is suitable when designing parallel special-purpose hardware, like systolic arrays.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 1991, 1. , 23 p.
SICS Research Report, ISSN 0283-3638 ; R91:15
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-21357OAI: diva2:1041393
Available from: 2016-10-31 Created: 2016-10-31

Open Access in DiVA

fulltext(2362 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 2362 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 4 hits
ReferencesLink to record
Permanent link

Direct link