JPH03137726A - Storage element allocation support device in architecture composite system - Google Patents

Abstract

PURPOSE:To generate a data pass which a designer intends in a process allocating a storage elements by providing a scheduling result storage means, a hardware resources storage means and a storage element designation means. CONSTITUTION:When the designer designates the set of variables or the storage elements through the storage element designation part 3 as to the possibility of making them common, a common possibility detection part 4 detects groups that can be made in common through the scheduling result storage part 1 and the hardware resources storage part 2. Namely, the detection part 4 detects the group which can be set common among the elements of the set of the variable or the storage elements based on information stored in the storage part 1 storing the execution schedule of an operation and that stored in the storage part 2 storing hardware resources which comes to be necessary. Since a detection result display part 5 displays a detection content, the designer can obtain information which can be set common among the designated variables and the storage elements, and design which the designer desires is easily executed on the allocation of the storage elements.

Description

DETAILED DESCRIPTION OF THE INVENTION [Object of the Invention] (Industrial Application Field) The present invention relates to a storage element allocation support device in an architecture synthesis system that supports hardware architecture design.

(Prior Art) In recent years, as digital systems have become larger in scale, various CAD systems have been developed with the aim of improving design efficiency. In particular, recently, architecture synthesis systems have emerged as systems that support functional design from a higher stage, which uses specifications expressed in software algorithms to manually generate the hardware configuration to realize the algorithms. ing.

Normally, in this architecture synthesis system, the designer focuses only on the processing algorithm he or she wants to implement, without being aware of the specific hardware configuration, and writes the hardware specifications using syntax similar to a general-purpose programming language. Describe. Then, the system manually writes such a specification description, extracts the orderliness and parallelism of the operations included in the specification description, determines the execution order of the operations (scheduling), and performs operations according to the execution order. Allocates the necessary hardware resources, ie, arithmetic units, registers, and transfer paths (data path allocation). A series of processes regarding these scheduling and data path assignments are automatically performed according to a certain algorithm without any intervention by the designer. For example, regarding the allocation of storage elements, see the following document 1).

2) The clique partitioning method shown in 2) and the Lert
The -edge method calculates the period (lifetime) during which variables are valid, and automatically merges those whose lifetimes do not overlap.

Reference 1) M, C, MeFar tand, ^, C, Parke
r, R, Camposano.

“Tutorial on 111gh-Level
5ynthesis”25th ACM/IEEE D
esign Automat1onConf'eren
ce, 1988. pp330-33B.

Reference 2) C, J, Tseng, D, P, 5levlorek.

“Automated 5 synthesis of D
ata Paths in Digital System
ms IEEE Transactions on CoBu
ter-^idedDesign, Vol1. CAD-5
, NO3, JULY 198B, pp379-395゜However, in the allocation of storage elements, the shape of the required transfer path changes by sharing the storage elements, so specifically, it is necessary to assign a selector to the input part of the storage element. It becomes necessary,
This includes the problem of an increase in the number of output fanouts, and it is necessary to carry out sharing while considering the trade-off with these effects. However, the above storage element allocation method There was a problem that little consideration was given to the impact, and as a result of sharing, an appropriate data path was not generated.

In particular, in the above method, each variable is shared as much as possible, so the variables selected at the beginning of the process are shared a lot, and the transfer path of the storage element corresponding to that variable is However, variables selected later in the process are not often shared, resulting in an unbalanced data path configuration.

In addition, since all sharing processing is left to the system, it is possible to say, "It seems better to use the same register for variables x and y," or "I want to implement variable KEY in the same register," or "variable .

There is also the problem that it is not possible to generate a data path configuration that meets the designer's judgment and intention, such as y and J, which should not be realized by the same register. Furthermore, it is not possible to use a design method in which a designer configures a data path through trial and error while also taking into account the effects of sharing storage elements.

As a result, the conventional architecture synthesis system has the problem of being difficult to use in actual design.

(Problems to be Solved by the Invention) As described above, in the conventional architecture synthesis system, the designer cannot intervene in data path allocation, and the data path intended by the designer cannot be generated. There was a problem.

Therefore, the present invention provides a storage element allocation support device for an architecture synthesis system that can generate a data path intended by a designer, especially in the process of allocating storage elements.
The purpose is to achieve 1+'-.

[Structure of the Invention] (Means for Solving the Problems) The present invention solves the above problems by manually writing hardware specification descriptions, extracting the order and parallelism of operations included in the descriptions, and determining scheduling and data paths. In a storage element allocation support device in an architecture synthesis system that performs allocation, as a means for allocating storage elements,
Scheduling result storage means for storing an execution schedule of calculations, hardware resource storage means for storing required hardware resources, storage element designation means for designating a set of variables or storage elements, and a collection of the variables or storage elements. sharing possibility detection means for detecting a set of elements for which storage elements can be shared; detection result display means for displaying detection results of the means; allocation specification means for specifying allocation of storage elements; specification of the means. and allocation execution means for allocating storage elements to the set designated by the storage element designation means based on the detection result of the sharing possibility detection means.

(Operation) In the storage element allocation support device in the architecture synthesis system of the present invention, when the designer specifies a variable or a set of storage elements, the information stored in the scheduling result storage means and the hardware resource storage means is used. The shareability detection means detects a set of elements in a set of variables or storage elements and presents the contents.As a result, the designer can select which of the specified variables or storage elements. It is possible to obtain information on which data can be shared and which data can be shared, and to allocate storage elements as intended based on this information.

(Example) Hereinafter, the present invention will be described in detail based on the drawings. FIG. 1 is a block diagram showing the configuration of a storage element allocation support device in an architecture synthesis system according to an embodiment of the present invention.

The storage element allocation support device of this example includes a scheduling result storage unit 1 that stores execution schedules for calculations of an architecture synthesis system, a hardware resource storage unit 2 that stores necessary hardware resources, and a storage element allocation support device that stores variables or storage elements. a storage element specifying unit 3 for specifying a set; a sharing possibility detection unit 4 for detecting a set of elements whose storage elements can be shared in a set of variables or storage elements;
a detection result display section 5 for displaying the detection result of , an allocation specification section 6 for specifying the allocation of storage elements, and a storage element specification section based on the specification of the means 6 and the detection result of the sharing possibility detection section 4 It has an allocation execution unit 7 that allocates storage elements to the set specified by 3. Further, the storage element allocation support device of this example includes a lifetime analysis section 8 disposed between the scheduling result storage section 1 and the storage element specification section 3, a control information display section 9, and a hardware resource storage section 2. A data path display section 10 is provided which is connected to.

The scheduling result storage unit 1 stores operations executed at each step of the architecture synthesis system in a directed graph as shown in FIG. The subscript M of the reference sign means memory.

In the directed graph shown in FIG. 2, nodes represent operations and edges represent data flows. As shown in the legend in Figure 3, a node has attributes such as the type of operation, the step in which the operation is executed, the unique number (id) of the arithmetic unit that executes the operation, the name of the variable that stores the result, and its bit width. It has a writing column. Nodes of operation type 1 represent input variables, and nodes of operation type O represent output variables. A blank attribute in a part of the storage element name or arithmetic unit ID indicates that the attribute has not been given yet. Note that the steps for input and output nodes are both 0.

The hardware resource recorder tti section 2 stores information on the assigned arithmetic units and storage elements as shown in FIG. That is, as shown in FIG. 5 as a legend, operations of the scheduling result storage section 1 using each arithmetic unit and variables of the scheduling result storage section 1 stored in each storage element are stored.

The control information display section 9 displays the contents of the scheduling result storage section 1 in a graph format on the CRT, as shown in FIG. A subscript in a reference sign means a screen. As shown as a legend in FIG. 7, in this display, the node indicates the calculation type, and in both examples, the step number and the calculation unit ID are respectively displayed. Also, the variable name is displayed below the node.

As shown in FIG. 8, the data path display section 10 displays on the CRT a data path for executing the operation of the scheduling result storage section 1 using the resources of the hardware resource storage section 2. In this display, variables whose storage elements are not shared are each displayed as a storage element with the same name as the variable name, except for input/output variables. Also,
A human variable such as reJ that is referenced in multiple steps is considered to require a storage element to hold the value, and is displayed as a storage element with the same name as the variable name.

The storage element specifying section 3 is a section for specifying variables or storage elements that the designer would like to know about the possibility of sharing.

The lifetime analysis section 8 analyzes the lifetime of the variable or storage element given by the storage element specification section 3.

The shareability detection unit 4 detects shareable combinations of the variables or storage elements specified by the storage element specification unit 3 based on the lifetime analysis results. The results are displayed on the CRT by the detection result display section 5.

The allocation designation section 6 is a section where the designer issues an instruction to allocate storage elements based on the detection result by the shareability detection section 4.

The allocation execution section 7 allocates storage elements based on the specifications of the allocation specification section 6, and assigns the storage elements to the scheduling result storage section 1. This is to change the contents of the hardware resource storage section 2.

In the above configuration, the scheduling result storage unit 1.
Considering the case where the information shown in FIGS. 2 and 4 is stored in the hardware resource storage unit 2, a specific example will be shown below.

Suppose that the designer, in the storage element specifying unit 3, specifies a variable whose sharability is to be investigated using the command shown in FIG. 9 while looking at the displays shown in FIGS. 6 and 8. The command in FIG. 9 uses the variable e.

Represents a designation to find a combination that can be shared among f, h, t, and j.

Then, the lifetime analysis unit 8 determines the steps in which assignments and references are made for the specified variables e, f, h, t, and j, and creates a lifetime table L shown in FIG.
Create TT. That is, as shown in Fig. 10, the symbol d is added to the step where a value is assigned to each variable.
Table L with the symbol r placed in the step where the reference was made
, make T.

The horizontal direction in FIG. 10 represents variables or allocated storage elements, and the vertical direction represents execution steps of operations.

Next, for each variable in FIG. 10, follow step 1 in order, and as shown in FIG. 11, mark the interval [d, r] and mark 1 interval [r, d].

Mark the interval [r, r], mark the remaining part,
Create a lifetime table LTT.

The shareability detection section 4 detects a set of variables that can be shared from the lifetime table LTT shown in FIG. 11, and the detection result display section 5 displays this as a graph as shown in FIG. 13.

The algorithm for creating the graph is shown in FIG.

That is, in step 1201, the lifetime table L
Let the variable appearing in TT be yj (j-1...N), create a node corresponding to this, and in step 1202 set j-1
In step 1203, the following process is executed until j<N.

First, in step 1204, it is determined whether there is one period with the symbol of variable yj. If there is one, the process moves to step 1207, and J = J + 1 is set, but 1
If not, proceed to step 12o5 and k−j+
1, and the process moves to step 12o6.

In step 1206, it is determined whether k<N, and if k<N, the process moves to step 1206.

If k<N is determined in step 1206, step 1
The process moves to 207, and it is examined whether variables yj and yk satisfy the following rule 1> or rule 2>.

Rule 1> In the variable yj and ykO sequences, periods with symbols do not overlap.

Rule 2> In the sequence of variables yj and yk, there are steps that both have symbols, and for all these steps, the variable yj
At this step, L ends, and the variable yk begins at this step.

If rule 1 or 2 is satisfied in step 1207, the process moves to step 1208, where nodes yj, y
Connect k. Also, if not satisfied, step 120
At step 9, - is set to +1 and the process returns to step 1206.

In FIG. 13, nodes of the graph represent variables, and edges represent that variables at both ends can share a storage element. Using this graph, the designer can check the variables specified by the command [There are no variables that can be shared with e]. J+
r', f+h can be shared. ” and other information.

Now, the designer can designate variables to be shared using commands as shown in FIG. 14 in the allocation specifying section 6 while viewing the display as shown in FIG. 6, FIG. 8, and FIG. 13. The command in FIG. 14 indicates that variables t, f, and h are to be stored in a register named R1.

Therefore, if the command shown in FIG. 14 is instructed, the allocation execution unit 7 first checks whether there are edges connecting the variables shown in FIG. 13 to each other, and if none of these edges exist. If the node representing the specified variable does not exist, it is assumed that the input in the assignment designation section 6 is incorrect, and an error message is output on the CRT. That is, the operands of the 5search command are limited to a subset of the variables currently displayed by the detection result display section 5.

In FIG. 13, since i and f are connected, and f and h are connected, respectively, the allocation execution unit 7 assumes that the manual input was correct, and according to the command in FIG. 14, the scheduling result storage unit 1. /% - Modify the contents of the hardware resource storage section 2.

The resulting storage contents of both storage units 1.2 are shown in FIGS. 15 and 16. In Figure 15, variables i, f
, the register name R1 is set to the node corresponding to h,
In FIG. 16, register R1 is added as a resource. 15 and 1 by the data path display unit 10.
FIG. 17 shows an example in which the information shown in FIG. 6 is displayed. In this way, the data path display section 10 allows the designer to confirm the data path resulting from sharing storage elements.

Here, when the storage element specifying unit 3 manually checks whether there are any more shareable variables by manually issuing a command as shown in FIG. 18, R1 is the variable i.

f and h, the lifetime analysis unit 8
The lifetime table LTT shown in FIG. 9 is created, and the detection result display section 5 displays a graph consisting of only isolated points as shown in FIG. 20 on the CRT. As a result, it can be seen that storage elements cannot be shared any more.

The display format on the detection result display section 5 is not limited to the graph shown in FIG. 13, but may be in a tabular format such as the matrix shown in FIG. 21, for example.

In the matrix of FIG. 21, a column in which O is displayed indicates that variables or storage elements corresponding to that row and column can be shared. Further, the detection result display section 5 may sequentially list variables or storage elements that can be shared with the variable or storage element specified by the storage element specification section 3. Additionally, when the number of specified variables or storage elements is large,
It is also possible to display the results for the next n variables each time the designer presses the return key, for example, by dividing the result into m times of n variables.

In this example, it is possible to know whether a specific variable or storage element can be shared by inquiring the system as to whether or not it can be shared.

Therefore, it is possible to allocate storage elements by trial and error based on the result of this inquiry.

In the above embodiment, when sharing a storage element, the allocation specification unit 6 issues an instruction again separately from the storage element specification unit 3. However, in the sharing possibility detection unit 4, the storage element specification unit 3 If it is determined that the variables and storage elements specified by one command can be realized by the same storage element, the allocation execution unit 7 can be automatically activated.

It is also possible to use a combination of conventional automatic methods. In other words, if the designer thinks, ``We have to have this kind of configuration. However, if the system appropriately allocates other parts using a conventional algorithm, it is possible to efficiently allocate storage elements in accordance with the designer's intention.

Furthermore, in this case, the designer can also specify in the allocation specification section 6 that sharing in subsequent processing is prohibited. For example, if a designer looks at the graph of the determination results in FIG. 13 and the display in FIG. By specifying this as umrg t, h;, the ID of the node whose sharing is prohibited is set in the allocation execution unit 6 as the node attribute of the variable 11 h of the scheduling result storage unit 1 (for example, the It is also possible to set node 10 to 7 and node 7 to 10), and in subsequent processing, refer to this attribute information to determine whether or not to perform sharing.

Furthermore, the system can automatically allocate only the variables and storage elements specified by the designer using one command in the storage element specifying unit 3 using a conventional algorithm. This also makes it possible to control the scope of sharing performed by the system.

The present invention is not limited to the above embodiments, and can be implemented with appropriate modifications without departing from the gist thereof.

[Effects of the Invention] As described above in detail, according to the present invention, based on the human power of the memory elements that are desired to be shared, it is determined whether or not the sharing is actually possible, and then the combination is appropriately selected. presentation,
Since this is a storage element allocation support device for an architecture synthesis system that accepts arbitrary sharing specifications, it is possible to easily design the storage element allocation as intended by the designer.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a storage element allocation support device in an architecture synthesis system according to an embodiment of the present invention;
FIG. 2 is an explanatory diagram of the storage contents of the scheduling storage unit;
Fig. 3 is an explanatory diagram of the legend, Fig. 4 is an explanatory diagram showing the storage contents of the hardware resource storage unit, Fig. 5 is an explanatory diagram of the legend, and Fig. 6 is a display example of the control information display unit. Explanatory diagram, Figure 7 is an explanatory diagram of the legend, Figure 8 is an explanatory diagram of a display example of the data path display section, Figure 9 is an explanatory diagram of commands in the storage element specification section, and Figure 10 is an illustration of lifetime table creation. Figure 11 is an explanatory diagram of a lifetime table, Figure 12 is a flowchart showing the procedure for creating a graph showing shareability, and Figure 13 is an explanatory diagram of a display example of the detection result display section. , FIG. 14 is an explanatory diagram of the command for sharing storage elements in the allocation specification section, FIG. 15 is an explanatory diagram of the storage contents of the scheduling result storage section after execution of the sharing command, and FIG. 16 is an illustration of the hardware after executing the same command. FIG. 17 is an explanatory diagram of a display example of the data path display unit after executing the same command; FIG. 18 is an explanatory diagram of a command for checking sharability;
Fig. 19 is an explanatory diagram of the lifetime analysis results, Fig. 20 is an explanatory diagram showing a display example when there is no possibility of sharing the detection result display section, and Fig. 21 is an explanatory diagram showing another display example of the detection result display section. FIG. 1... Scheduling result storage section 2... Hardware resource storage section 3... Storage element specification section 4... Sharability detection section 5... Detection result display section 6... Allocation specification section 7 ... Allocation execution section 8 ... Lifetime analysis section 9 ... Control information display section 10 ... Data path display section

Claims (2)

[Claims] (1) As a means for allocating storage elements in a storage element allocation support device in an architecture synthesis system that inputs a hardware specification description, extracts the orderliness and parallelism of operations included in the description, and performs scheduling and data path allocation. , a scheduling result storage means for storing an execution schedule of an operation, a hardware resource storage means for storing necessary hardware resources, a storage element specifying means for specifying a set of variables or storage elements, and in the set of variables or storage elements. sharing possibility detection means for detecting a set of elements whose storage elements can be shared; detection result display means for displaying the detection results of the means;
Allocation specifying means for specifying the allocation of storage elements; allocation execution means for allocating storage elements to the set specified by the storage element specifying means based on the specification of the means and the detection result of the sharing possibility detection means; A storage element allocation support device in an architecture synthesis system characterized by having the following features: (2) In the storage element allocation support device in an architecture synthesis system according to claim 1, when the architecture synthesis system includes means for automatically allocating storage elements, the allocation specification means is configured to share 1. A storage element allocation support device in an architecture synthesis system, characterized in that it is possible to specify that structuring is prohibited.