The derivation of systolic implementations of programs

Summary We present a mathematically rigorous and, at the same time, convenient method for systolic design and derive systolic designs for three matrix computation problems. Each design is synthesized from a simple program and a proposed layout of processors. The synthesis derives a systolic parallel execution, channel connections for the proposed processor layout, and an arrangement of data streams such that the systolic execution can begin. Our choices of designs are governed by formal theorems. The synthesis method is implementable and is particularly effective if implemented with graphics capability. Our implementation on the Symbolics 3600 displays the resulting designs and simulated executions graphically on the screen. The method's centerpiece, a transformation of sequential program computations into systolic parallel ones, has been mechanically proved correct.Parts of this work have been presented at the Conference on Parallel Architectures and Languages Europe (PARLE) [10]. This research has been supported in part by Grant No. 26-7603-35 from the Lockheed Missiles & Space Corporation and by Grant No. DCR-8610427 from the National Science Foundation     

Statement-Level Communication-Free Partitioning Techniques for Parallelizing Compilers

This paper addresses the problem of communication-free partition of iteration spaces and data spaces along hyperplanes. To finding more possible communication-free hyperplane partitions, we treat statements within a loop body as separate schedulable units. Instead of using the information about data dependence distance or direction vectors, our technique explicitly formulates array references as transformations from statement-iteration spaces to data spaces. Based on these transformations, the necessary and sufficient conditions for communication-free partition along hyperplanes to be feasible have been proposed. This approach can be applied to all programs with an imperfectly nested loop or sequences of imperfectly nested loops, whose array references are affine functions of outer loop indices or loop invariant variables. The proposed approach is more practical than existing methods in finding the data and computation distribution patterns that can cause the processor to execute fully-parallel on multicomputers without any interprocessor communication.     

An incremental mechanical development of systolic solutions to the Algebraic Path Problem

Summary The Algebraic Path Problem, whose solution is Gauss-Jordan elimination, is one of the most complex problems for which systolic implementations have been proposed. We apply a development method which derives these systolic implementations from a traditional (i.e., Pascal-like) program by formal computational steps. The structure which our method imposes on the derivation process exposes clearly the relationship between the different implementations.This research was partially supported by Grant No. 26-7603-35 of the Lockheed Missiles & Space Corporation and by Grant No. DCR-8610427 of the National Science FoundationThe main results of this work have been presented at the 1 st Int. Conf. on Computer Technology, Systems and Applications (CompEuro 87)     

Reuse-Driven Tiling for Improving Data Locality

This paper applies unimodular transformations and tiling to improve data locality of a loop nest. Due to data dependences and reuse information, not all dimensions of the iteration space will and can be tiled. By using cones to represent data dependences and vector spaces to quantify data reuse in the program, a reuse-driven transformational approach is presented, which aims at maximizing the amount of data reuse carried in the tiled dimensions of the iteration space while keeping the number of tiled dimensions to a minimum (to reduce loop control overhead). In the special case of one single fully permutable loop nest, an algorithm is presented that tiles the program optimally so that all data reuse is carried in the tiled dimensions. In the general case of multiple fully permutable loop nests, data dependences can prevent all data reuse to be carried in the tiled dimensions. An algorithm is presented that aims at localizing data reuse in the tiled dimensions so that the reuse space localized has the largest dimensionality possible.     

An integrated information system for real estate agency-based on service-oriented architecture

To enhance the efficiency of surfing the Internet, an integrated platform for real estate agency-based on service-oriented architecture (SOA) is established. It employs the concept of search engine and loads the information provided previously by each real estate agency to this platform. Due to the different types of data structure from each real estate agency website, the standard format must be defined for integrating the information. In this paper, the standard is defined by XML and is used to integrate heterogeneous database. This standard format includes the data fields that are required by the agency websites. It is processed in the platform which is expandable by receiving information from other sources in the future. In consideration of the copyright regulation, the agents are allowed to login and to share specific information on this platform in order to increase the transaction rate. The system also includes a Google Map engine for GIS service that marks the spatial location as the users send the requests. It helps the users to find the demanded housing information and to retrieve the nearby geographic location in a very short time.