AN INTEGRATED APPROACH TO RESOURCE ALLOCATION IN HIGH-LEVEL SYNTHESIS

Abstract

High-level synthesis is one of the three phases in automatic synthesis. Its job is to synthesize hardware structures from the behavioural description given. The high-level hardware design produced is then synthesised further into actual, low-level, hardware implementation via the other two phases, logic synthesis and layout synthesis. High-level synthesis consists of scheduling and resource allocation. The input to high-level synthesis is a data-flow graph which captures the behavioural description. While scheduling decides the time at which the different operations in this graph are performed, resource allocation produces the hardware data-path that can perform all the operations at their scheduled times. Resource allocation is a complex problem. It consists of three interdependent. tasks, register allocation and binding, functional-unit allocation and binding and interconnection allocation and binding. In this thesis we study the resource allocation problem and devise an algorithm for automating its solution. We assume that scheduling is performed first, and then the "consumers" (variables, operations and data-flows) are allocated and bound to appropriate "resources" (registers, functional-units and interconnects). The aim of resource allocation is to minimise the cost of the hardware data-path produced. There are two main approaches for resource allocation in the literature: those that model the tasks as an ILP problem, and those that adopt heuristic: approaches. As the algorithm for solving ILP problems take exponentiaI time, we focus on the heuristic approaches, most of which currently performing resource allocation, Ly performing the three allocation tasks sequentially. Even those that attempt to perform the allocation tasks concurrently, do so in some other order, eg control-step order. Furthermore, the cost model adopted by most of the algorithms are local. Decisions are not made from a global perspective. Hence, the effective impact of a decision on all the different allocation components is not considered. It is our assessment that taking a course-grained approach, ie performing resource allocation by performing the three tasks in some order, is not effective. With a large amount of interdependence between the three allocation tasks and a large problem size, this constraint, of completing one task before moving to the next one, can cause the algorithms to make short sighted decisions, resulting in poor allocation solutions eventually. The local cost model compounds the problem faced when making allocation decisions, further. In this thesis, we define a new approach and cost model for performing resource allocation. If we look at the resource allocation task as making a series of decisions, ie selecting a consumer at each step and assigning it to a resource, the aim is to make the best decision each time. Hence, we propose a fine grained approach, where we look at resource allocation as a set of decision subtasks. At each step, we perform the best decision subtask, irregardless of which of the three tasks it belongs to. The constraint of course grained approaches is effectively removed, and we make our decision at each step by looking at the whole decision space for the problem. The resulting algorithm integrates the three allocation tasks together. To make the best decision, we also propose a new global cost model. The aim is that when computing decision costs, we want the cost to reflect how confident we are that it is the best decision from the global perspective. The direct impact of a decision on the data-path is computed first, and we call this the local cost of that decision. We then apply a novel 'competition' algorithm, which effectively considers the entire decision space, and converts the local cost to a global cost. Hence, we have two key contributions in this thesis : 1. We propose a new, fine grained and concurrent framework for resource allocation. The algorithm devised by us using this framework is called CCR. 2. We derive a simple yet effective means for converting the local cost of a decision, into a global cost. We developed a high-level synthesis system called HARDWIRE. It was developed on the PC platform using Linux. It was implemented using C++ and Perl. Our new algorithm CCR was developed as part of the allocation module of this system, along with several other allocation algorithms implemented by us. All our experiments were conducted using HARDWIRE. Our experiments have proven that our new algorithm performs very well. It outperforms the well known Tseng's algorithm [TsSi86] almost all the time. The quality of the solutions produced by CCR, for the problem sizes we have tested, are between 5% to 11% better when compared to the solutions produced by Tseng's Algorithm. The experiments also show that the fine grained approach taken by us, performs better than all the other course grained approaches we tested against.