Efficient cycle-based reconfiguration of datapaths can be realized on current FPGAs by designing merged datapaths, which can execute different tasks depending on the datapath control. In our previous work, we provided a synthesis tool for the automated generation of such datapaths. The objective in this paper is a reduction of the resource requirements for implementing the reconfiguration control on the FPGA. First, we extend our existing tool flow with a novel mechanism for efficient partial multi-context reconfiguration and provide tool support to generate according circuitry, control, and configuration data. Second, we propose an extension of current FPGA architectures to efficiently support cycle-based runtime control. We employ a special content-addressable multi-context memory resource for controlling the datapath functionality, which on average requires only 15% memory for storing the control data compared to a BlockRAM based approach, and only 53% compared to regular multi-context switching.

In this paper a systematic mapping method for a specific algorithm class is given which exploits all levels of parallelism of the target architecture. This target architecture is a processor array where each processing element can have several functional units. This functional units allow subword parallelism, that means multiple equal operations with low data word width can be executed in parallel in the data path of the functional units. The mapping method is illustrated on the edge detection algorithm, and achieves up to 99 % of the theoretical speed-up.

In this booth on fine grain reconfigurable architectures, several research groups demonstrate their joint work on operating concepts for managing dynamic and partial reconfiguration, visualization of bitstreams and routing, presenting an application applying dynamic reconfiguration for video engines as well as work on minimization of reconfiguration data. Unique is that all the above four projects present their work using the same reconfigurable FPGA-based fabric called Erlangen slot machine that has also been built within one project just the purpose of experimenting with dynamic fine grain reconfiguration as an interdisciplinary platform.

We present new approach to optimize circuits for dynamic reconfiguration in FPGAs. Within a high level synthesis tool we optimize the binding of operations to resources to achieve high re-use of resources and interconnect between different configurations. We demonstrate that reconfiguration costs can be drastically reduced, while adding a small area overhead. Moreover, our method can merge several tasks into area efficient, static implementations. Both methods allow us to find new trade-offs between resource requirements and reconfiguration costs in dynamic application scenarios.

Dynamic reconfiguration for fine grained architectures is still associated with significant reconfiguration costs. In this paper we propose a new reconfiguration aware design flow. The tools in this flow implement a set of tasks concurrently. The flow leads to task implementations with minimal costs for routing reconfiguration. This is mainly achieved by our mapping tool which solves two fundamental problems: our mapping algorithm generates variants for the mapping of netlist cells to logic blocks. From those logic blocks a subset for each task is selected that minimizes the cost for routing reconfiguration. We derive a cost function and formulate an integer linear program to solve this problem. We implemented several task sets with our method and compare the results to previous solutions. We show that the reconfiguration aware mapping leads to better results than early approaches with vendor provided tools.

In the process of mapping compute-intensive algorithms onto arrays of processing elements (PEs) an efficient usage of channels between PEs and registers within PEs is crucial for achieving a significant algorithm acceleration. In this paper this problem is solved for algorithms represented as systems of uniform recurrence equations. We address an optimization problem in order to realize the algorithmic data dependencies within the processor array (PA) with minimum cost for channels and registers. There, we use a new mapping approach which allows a direct mapping of the algorithm onto the PA by a partitioning method. In contrast to existing approaches, we consider the issue of avoiding redundant usage of channels and registers, which can appear if one instance of a variable has to be transferred from a source PE to several sink PEs. Further, a solution of the optimization problem determines the schedule for the transfer of the variable instances in the channels and their storage in registers as well as the inner schedule for the operations in the PEs. We illustrate our method on the edge detection algorithm.

Reconfiguration of tasks implies considerable overhead on the amount of configuration data and time. Much overhead is caused by redundant configuration generated by the design tools which implement similar structures in the designs on different resources. In this paper, we propose a new method to identify structural similarities in tasks. Based on this information, we are able to generate automatically constraints to ensure that the place and route tools use identical resources. Thus we ensure that less redundant configuration is produced. In this paper, we give a formal description of the underlaying maximum edge matching problem and show a method to solve it optimally. We derive a truncation criteria to restrict the search space efficiently. We also propose an ant colony optimization based solution with a problem specific local heuristic and show that it performs optimal as well in our examples, but with considerable lower computational effort

Upcoming processor generations increasingly provide instructions for sub-word parallelism. Thus, a parallel execution of 2, 4 or 8 instructions (add, sub) or of complex instructions (sum of differences) with an input of 2, 4 or 8 operand pairs becomes possible. The exploitation of sub-word parallelism is still weakly supported by current compilers. To remedy this we have adapted methods from the design of parallel regular processor arrays. The causality constraints which influence the design flow of processor arrays can be relaxed for processors with sub-word parallelism. An algorithm calculating the Mahalanobis distance is used to illustrate the influence. Based on this extended approach, we have obtained significant speed-ups of our test-vehicle, of up to a factor 3 on an Intel P4. In the conventional approach, assembly-level coding would have been required to achieve this.

The object of algorithm design in context with a hierarchically structured memory system is a reduction of access cycles to higher memory levels by an increase of data reuse from levels closer to execution units. The object of our approach is to systematically construct an algorithm coding, starting from a weak single assignment form, so that parameters of the algorithm code (number and type of partitions, scheduling orders) can be directly mapped on parameters of the architecture (number of memory levels, size of the memories, input/output access behavior) and vice versa. Target architectures are processors with from one up to a few execution units and with a hierarchically structured memory system. The approach is based on methods derived from the realm of array synthesis and consists of a recursively defined algorithm partitioning. An approach to a quantitative determination of data reuse in recursively partitioned algorithms is given.

We consider a balanced combined application of the known LPGS- and LSGP-partitioning which we call co-partitioning. This approach allows a structural adjustment of the array design as well as a balancing of the size of the local memory and the IO-demand between the processing elements of the co-partitioned array. We determine the size of the LSGP-partitions such that there exists a sequential scheduling within the LSGP-partitions which is free of wait states. We give the proof for the existence of such a scheduling, and we give explicit formulas for the lower and upper bounds of the loops of a for-loop program which represents one of the possible sequential schedulings.

In this paper the inclusion of hardware constraints into the design of massively parallel processor arrays is considered. We propose an algorithm which determines an optimal scheduling function as well as the selection of components which have to be implemented in one processor of a processor array. The arising optimization problem is formulated as an integer linear program which also takes the necessary chip area of a hardware implementation into consideration. Thereby we assume that an allocation function is given and that a partitioning of the processor array is required to match a limited chip area in silicon.