1. Field of the Invention
The present invention relates to a technique for processing a data flow graph necessary for configurable the operation of a reconfigurable circuit with variable functions.
2. Description of the Related Art
Recently, efforts have been made toward the development of a reconfigurable processor in which the hardware operation is changeable in accordance with a target application. In building architecture that implements a reconfigurable processor, a digital signal processor (DSP) or a field programmable gate array (FPGA) is used.
A field programmable gate array (FPGA) allows relatively flexible circuit configuration by permitting circuit data to be written after a large-scale integration (LSI) is fabricated. FPGAs are used to design dedicated hardware. An FPGA includes basic cells each comprised of a look-up table (LUT) for storing a truth table of a logic circuit and an output flip-flop and of programmable wiring resources connecting between basic cells. In an FPGA, a desired logic operation is achieved by writing data for storage in the LUT and by writing wiring data. Designing an LSI by using an FPGA, however, results in a larger mounting area and a higher cost than designing it with an application specific integrated circuit (ASIC). To address this, there has been proposed a method designed to reuse circuit configurations by dynamically reconfiguring an FPGA (see, for example, JP Hei10-256383 A).
For example, satellite broadcasting is operated by switching between different broadcast modes depending on the season. The hardware of a receiver adapted to this is built with a plurality of circuits for respective broadcast modes. A selector is used to switch between the circuits to receive in the broadcast mode selected. Therefore, the circuits for the other broadcast modes remain idle all the while. In a situation like mode switching, where normally a plurality of dedicated circuits are switchably used and an interval between switching events is relatively long, the LSI may be reconfigured instantaneously when switching between modes, instead of building a plurality of dedicated circuits. In this way, circuit configuration is simplified and versatility is enhanced. The mounting cost is reduced at the same time. Dynamically reconfigurable LSIs have been the focus of attention in the industry as a measure to meet the above-mentioned needs. Particularly, it is essential that LSIs installed in a mobile terminal such as a cell phone and a personal data assistant (PDA) be small-sized. By dynamically reconfiguring the LSI and switching between functions in accordance with the required use, the mounting area of the LSI is prevented from growing.
An FPGA is characterized by flexible circuit configuration design and versatility. Meanwhile, it needs to include a control circuit for controlling the on and off conditions occurring between a large number of switches, in order to permit connections between all basic cells. This will inherently increase the mounting area of the control circuit. Also, since a complex wiring pattern is developed for connection between basic cells, the wiring tends to be long. Moreover, the structure in which a large number of switches are connected to a single wire gives rise to a long delay. For these reasons, FPGA-based LSIs are generally used for testing and experimenting purposes only and are not suited to mass production, considering the mounting efficiency, performance and cost. Another problem is that, since configuration information needs to be transmitted to a large number of basic cells of LUT-based logic implementation, it takes a considerable period of time to configure the circuit. For this reason, an FPGA is not suitable for usage in which instantaneous switching between circuit configurations is needed.
To address these issues, studies have been made recently into an ALU array in which a plurality of units called arithmetic logic units each with multiple operating functions are provided in multiple rows. In an ALU array, process flows downward only so that wiring connecting ALUs in the horizontal direction is not necessary. This makes it possible to achieve circuit scale smaller than that achievable by FPGAs.
In an ALU array, the configuration for the operating functions of the ALU circuits and the wiring in a connection unit for connecting between front and back-end ALUs are controlled by command data so as to perform desired processes. The command data is generated from information in a data flow graph (DFG) created from a source program described in a high-level language such as C.
The size of a DFG mapped into the ALU array at a time is limited by the circuit scale of the ALU array. Therefore, a large DFG needs to be divided into a plurality of DFGs for later joining. The size of a DFG generated by joining directly affects the number of circuit configurations executed in the ALU array. Accordingly, it is preferable that the size be as small as possible.