This paper presents a set of measurements that characterize the design space for automatically mapping high-level algorithms consisting of multiple loop nests, expressed in C, onto an FPGA. We extend a prior compiler algorithm that derived optimized FPGA implementations for individual loop nests. We focus on the area-time tradeoffs associated with sharing constrained chip area among multiple computations represented by an asynchronous pipeline. Intermediate results are communicated on chip; communication analysis generates this communication automatically. Other analyses and transformations, also associated with parallelizing compiler technology, are used to perform high-level optimization of the designs. We vary the amount of parallelism in individual loop nests with the goal of deriving an overall design that makes the most effective use of chip resources. We describe several heuristics for automatically searching the space and a set of metrics for evaluating and comparing designs. From results obtained through an automated process, we demonstrate that heuristics derived through sophisticated compiler analysis are the most effective at navigating this complex design space, particularly for more complex applications.

We describe a generalized approach to deriving a custom data layout in multiple memory banks for array-based computations, to facilitate high-bandwidth parallel memory accesses in modern architectures, where multiple memory banks can simultaneously feed one or more functional units. We do not use a fixed data layout, but rather select application-specific layouts according to access patterns in the code. A unique feature of this approach is its flexibility in the presence of code reordering transformations, such as the loop nest transformations commonly applied to array-based computations. We have implemented this algorithm in the DEFACTO system, a design environment for automatically mapping C programs to hardware implementations for FPGA-based systems. We present experimental results for five multimedia kernels that demonstrate the benefits of this approach. Our results show that custom data layout yields results as good as, or better than, naive or fixed cyclic layouts, and is significantly better for certain access patterns and in the presence of code reordering transformations. When used in conjunction with unrolling loops in a nest to expose instruction-level parallelism, we observe greater than a 75% reduction in the number of memory access cycles and speedups ranging from 3.96 to 46.7 for 8 memories, as compared to using a single memory with no unrolling.

In this paper, we describe a set of compiler analyses and an implementation that automatically map a sequential and un-annotated C program into a pipelined implementation, targeted for an FPGA with multiple external memories. For this purpose, we extend array data-flow analysis techniques from parallelizing compilers to identify pipeline stages, required inter-pipeline stage communication, and opportunities to find a minimal program execution time by trading communication overhead with the amount of computation overlap in different stages. Using the results of this analysis, we automatically generate application-specific pipelined FPGA hardware designs. We use a sample image processing kernel to illustrate these concepts. Our algorithm finds a solution in which transmitting a row of an array between pipeline stages per communication instance leads to a speedup of 1.76 over an implementation that communicates the entire array at once.

Reconfigurable systems, and in particular, FPGA-based custom computing machines, offer a unique opportunity to define application-specific architectures. These architectures offer performance advantages for application domains such as image processing, where the use of customized pipelines exploits the inherent coarse-grain parallelism. In this paper we describe a set of program analyses and an implementation that map a sequential and un-annotated C program into a pipelined implementation running on a set of FPGAs, each with multiple external memories. Based on well-known parallel computing analysis techniques, our algorithms perform unrolling for operator parallelization, reuse and data layout for memory parallelization and precise communication analysis. We extend these techniques for FPGA-based systems to automatically partition the application data and computation into custom pipeline stages, taking into account the available FPGA and interconnect resources. We illustrate the analysis components by way of an example, a machine vision program. We present the algorithm results, derived with minimal manual intervention, which demonstrate the potential of this approach for automatically deriving pipelined designs from high-level sequential specifications.

Article In-memory directories: eliminating the cost of directories in CC-NUMAs Share on Authors: Christopher Ho Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile , Heidi Ziegler Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile , Michel Dubois Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architecturesJune 1998 Pages 222–230https://doi.org/10.1145/277651.277688Online:01 June 1998Publication History 1citation228DownloadsMetricsTotal Citations1Total Downloads228Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access