Affordable Access

Implementation strategies for single assignment variables

Publication Date
  • Computer Science


Implementation Strategies for Single Assignment Variables Frej Drejhammar1,2 Christian Schulte1 1 IMIT, KTH - Royal Institute of Technology, Sweden 2 SICS - Swedish Institute of Computer Science, Sweden {frej,[email protected] Abstract Flow Java integrates single assignment variables (logic variables) into Java. This paper presents and compares three implementation strategies for single assignment variables in Flow Java. One strategy uses forwarding and dereferencing while the two others are variants of Taylor’s scheme. The paper introduces how to adapt Taylor’s scheme for a concurrent language based on operating system threads, token equality, and update of data structures. Evaluation of the strategies clarifies that the key issue for efficiency is reducing memory usage. 1 Introduction Flow Java attempts to simplify concurrent programming in Java by conservatively extending Java with single assignment variables (logic variables). Clearly, the most important aspect of imple- menting Flow Java concerns maintaining single assignment variables. Motivation, related work, and an implementation based on forwarding and dereferencing are presented in [2]. This paper discusses and compares three different implementation strategies for single assign- ment variables in Flow Java. In addition to the forwarding scheme, we discuss two schemes based on maintaining aliased (equal but not yet bound) single assignment variables in a circular data structure originally due to Taylor [10]. Other approaches based on Taylor’s scheme are [4, 9, 8]. They have in common that they carefully investigate the interaction with search by optimizing trailing. This paper naturally takes a different perspective. Firstly, Flow Java implements concurrency with operating system threads. This means that all operations on variables must take this concurrency model into account and use locking to guarantee atomicity. Locking is made deadlock free by exploiting ordering of objects in memory. This is dif

There are no comments yet on this publication. Be the first to share your thoughts.