ISSN:1063-7192    

DOI:10.1080/01495730008947353

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

The design and implementation of a library of C-code procedures to perform operations on rational polyhedra is described. The library supports intersection, union, difference, simplification in context, convex hull, affine image, affine preimage, and computation of dual forms. Since not all of these functions are closed over polyhedra, the library is extended to operate on finite unions of polyhedra. The major design decisions made during the implementation of the library are discussed. The data structure used for representing finite unions of polyhedra is developed and validity rules for the representation of polyhedra are derived. And finally, the algorithms used to implement the various functions in the library are presented.

ISSN:1063-7192    

DOI:10.1080/01495730008947354

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

Minimizing the amount of time and number of processors needed to perform an application reduces the application's fabrication cost and operation costs. A directed acyclic graph (dag) model of algorithms is used to define a time-minimal schedule and a processor-time-minimal schedule, We present a technique for finding a lower bound on the number ofprocessorsneeded to achieve a given schedule of an algorithm. The application of this technique is illustrated with a tensor product computation. We then apply the technique to the free schedule of algorithms for matrix product, Gaussian elimination, and transitive closure. For each, we provide a time-minimal processor schedule that meets these processor lower bounds, including the one for tensor product.

ISSN:1063-7192    

DOI:10.1080/01495730008947355

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

In this paper an approach is presented to combine the design of background memory architectures and processor arrays for data dominated real-time applications. The formalized data transfer and storage exploration (DTSE) approach of IMEC involves a methodology for the design of a low-power small-size background memory organizations, meeting real-time constraints. The systematic space-time transformation and the subsequent co-partitioning approach of the Dresden University of Technology, allow the design of realistic processor arrays adapted to a given memory architecture. However, neither methodology can derive on its own the complete solution of a fully optimized memory organization, combining background and foreground memory. Extensions to enable this important problem will be presented here. First, both complementary methodologies will be summarized. Next, the main emphasis in this paper will be on the approach to design the processor array within the context of an already optimized and hence given memory architecture. The feasibility of the proposed combination is demonstrated on a representative test-vehicle for an important class of applications, namely a full motion estimation kernel in MPEG.

ISSN:1063-7192    

DOI:10.1080/01495730008947356

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

Most automatic parallelizes are based on the detection of independent operations. Dependence analysis is mainly a syntactical process, in which the actual data transformations are ignored. There is another source of parallelism, which relies on semantical information, namely the detection of reductions and scans. Scans and reductions are quite frequent in scientific codes and are implemented efficiently on most parallel computers. We present here a new Scan detector which is based on the normalization of systems of recurrence equations. This allows the detection of scans in loops nests of arbitrary depth and on multi-dimensional arrays, and gives a uniform treatment for scalar reductions, array reductions, and arrays of reductions.

ISSN:1063-7192    

DOI:10.1080/01495730008947357

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

In this paper, we introduce a model called regular state machines (RSMs) that characterizes a class of state transition systems with regular transition behavior. It turns out that many process graph models such as synchronous dataflow graphs and Petri nets have a state transition system that may be described and analyzed in the RSM model.

ISSN:1063-7192    

DOI:10.1080/01495730008945375

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor