Overview

Excerpt from Compilation Techniques for Vliw Architectures Experiments have shown that reasonable amounts of fine grain parallelism are available globally in serial programs. New compaction algorithms, as well as a new architecture, have been put forward to exploit such parallelism. Due to its global nature, ordinary local compaction techniques are inadequate to fully extract the fine grain parallelism available in serial programs. Three global compaction algorithms are presented: 1. Trace scheduling compacts the most probable execution paths of a program, using some local compaction algorithm. Compensation code is inserted to preserve semantic equivalence with the original program. 2. Percolation scheduling is based on a series of elementary semantic-preserving program transformations which are repeatedly applied using higher level guidance rules. 3. Region scheduling evenly redistributes the parallelism available throughout a program, taking into account machine capabilities. Parallelism redistribution is again achieved via repetitive application of elementary program transformations. Global compaction algorithms alone are insufficient to speedup loops effectively, since after compaction loops iterations are still executed serially. A new compilation technique, software pipelining (the software version of hardware pipelining), overcomes this problem by overlapping successive iterations as much as possible. Several software pipelining algorithms are presented, some achieving optimal or quasi-optimal overlapping in the absence of resource constraints. The idea behind software pipelining algorithms is to (explicitly or implicitly) determine the (fixed or variable) time interval which must be respected before starting the execution of a new iteration. Most of the algorithms create a rigid pipeline, that is iterations are scheduled when the compiler is certain that they will execute without interruptions. More flexible pipelining algorithms are also presented. The above compilation techniques have been developed for a specific type of architecture termed very long instruction word (VLIW) architecture. VLIVVs vaguely resemble horizontal microengines, but their structure is cleaner and their instruction set more orthogonal. Three sorts of VLIW machines, based on three different computational models are presented. All three computational paradigms allow multiple operations and multiple conditional branches per machine instruction. What distinguishes the models is the way multiple conditional branches are handled. The first model was specifically designed to accommodate trace scheduling: semaiitically multiple conditional jumps are organized like in a Lisp cond statement. The second model, used by percolation scheduling, allows multiple conditional jum to have the structure of an arbitrary decision tree. The last model extends percolation scheduling by allowing conditional register assignments to be performed within a decision tree. This model is used to generate flexible software pipelines. About the Publisher Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.

Full Product Details

9781332115044

Table of Contents

Reviews

Author Information

Tab Content 6

Customer Reviews

Recent Reviews

Countries Available