Queue Machines | Data Structures and Algorithms with Object-Oriented Design Patterns in Java (Worldwide Series in Computer Science)

Website of Bruno R. Preiss

Next : Effective Memory Bandwidth of Up: Unpublished Manuscripts Previous: Yaddes-Yet Another Distributed Discrete

Bruno R. Preiss. manuscript 10 pp.[24].

Two formal execution models that use a queue as the underlying data structure for the manipulation of operands and results are presented. They are the ``simple queue machine'' and the ``indexed queue machine.'' An algorithm for generating the instruction sequence for evaluating an arbitrary expression on a simple queue machine is presented. It is shown that simple queue machines can efficiently exploit pipelined ALUs and support efficient concurrent expression evaluation.
Acyclic dataflow graphs are shown to naturally lead to the generation of instruction sequences for the indexed queue machine execution model. Since queue machines are statically scheduled, they can exploit the techniques of conventional, Von Neumann architectures such as instruction look-ahead and overlapped execution of sequential instructions, thus overcoming a shortcoming of dataflow execution models. Practical indexed queue machines can be implemented by using registers that act as a cache for the front of the operand queue.

external Full text.