Hierarchical memory synthesis in reconfigurable computers

Abstract

A Reconfigurable Computer (RC) is a hardware platform that typically includes several programmable devices, memory devices, and possibly specialized devices such as analog-to-digital converters. Such high-performance platforms are capable of accommodating large designs while avoiding the time-to-market associated with ASIC implementations. This work addresses the process of mapping data structures of an application onto the storage elements of RCs with hierarchical memories. In order to optimize the placement of data, several aspects of data mapping are addressed. Input specification styles and synthesis-related issues, physical resource conflicts and arbitration issues, several memory mapping techniques, and interaction between memory mapping and logic partitioning are presented and discussed. The state-of-the-art in reconfigurable computers and their memory subsystems is reviewed and RCs are classified based on their architectures. The importance of hierarchical memories in RCs and the trend in increasing complexity is discussed. A specification model that is well-suited for the memory mapping problem is introduced and the synthesis mechanism involved is described. Several memory mapping techniques are presented and their applicability on existing hardware platforms is discussed. Integer Linear Programming (ILP) formulations are used and assignment techniques that cater to different RC features are developed. With this Technique, small to medium sized designs are solved in a reasonable amount of time. Furthermore, these solutions are optimal. On the other hand, with large sized designs, these ILP techniques become time consuming. Because of their slow execution speed and the complexity of the problem, a novel methodology that speeds up the execution while retaining a high mapping quality is introduced. This methodology divides the mapping process into two, global/detailed, sequential steps (ILP-based) and produces fast mappings at a relatively small quality cost. One important issue when dealing with the memory assignment problem is resource conflicts. If the number of physical memories on the RC is limited, the assignment is forced to reuse these resources thus creating access conflicts. This problem is presented and an efficient arbitration solution that is well-suited for RC environments is proposed and implemented. Finally, memory mapping techniques are extended to interface with logic partitioning tools. A full spatial partitioning framework is presented where memory mapping interacts with logic partitioning and optimizes the overall placement of both computations as well as data in the design.