JP2014225200A - Semiconductor device design apparatus, semiconductor device design method, and semiconductor device design program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a semiconductor device design apparatus, a semiconductor device design method, and a semiconductor device design program capable of preventing a redundant array access from being added during a behavioral description, preventing an increase in an area of generated hardware, and achieving high speed operation.SOLUTION: An analysis unit analyzes a reuse relation between array accesses from a behavioral description stored in a storage unit on the basis of a subscript and conditions of a conditional statement, and calculates a data reuse distance between the array accesses, a difference in the reuse distance between the array accesses, and conditions of occurrence of the reuse of the array accesses. A first processing unit adds a circulation buffer description or a shift register description on the basis of the difference in reuse distance and a specified value. A second processing unit replaces the array access with a temporary variable access representing input/output terminals of the shift register or the circulation buffer, adds a conditional statement, and generates an optimized behavioral description.

Description

  The present invention relates to a semiconductor device design apparatus, a design method, and a design program for optimizing a behavior level description (hereinafter simply referred to as a behavior description) in which an operation of a digital circuit is described.

  The high-level synthesis technology (Non-patent Document 1) can automatically generate an RTL (Register Transfer Level) description from an operation description (hereinafter also referred to as C description) configured by a program such as C language. ) Design efficiency can be greatly improved. However, in order to generate a high-performance RTL description, it is usually necessary to optimize memory access on the C description. Currently, optimization of memory access by a high-level synthesis tool requires the user of the high-level synthesis tool to manually optimize the C description, which increases design time.

  One technique for optimizing memory access is a technique called scalar replacement (Non-Patent Documents 2, 3, and 4). The array and temporary variable in the C description are a memory and a register on the hardware. The scalar replacement is a technique that replaces access to a plurality of arrays in a C description with access to a temporary variable, that is, access to a memory with access to a register. By applying the scalar replace to the C description before the high-level synthesis, it is possible to reduce the memory access of the automatically generated hardware and to improve the performance.

  However, the most versatile technique among the existing scalar replaces (Non-Patent Document 3) does not strictly analyze the execution conditions of array access, and therefore, there are cases where memory access cannot be replaced with register access. As a result, the area of the generated hardware increases, and the operation speed may decrease.

JP 2012-118835 A

Daniel D. Gajski, “High Level Synthesis: An Introduction to Chip and System Design,” Kluwer Academic Publishers, 1992. Steve Carr, Ken Kennedy, “Scalar Replacement in the Presence of Conditional Control Flow,” Software-Practice and Experience, Vol. 24, Issue 1, pp. 51-77, 1994. Byoungro So, “An Efficient, Design Space Exploration For Balance Between Computation And Memory”, Ph.D.dissertation, University of Southern California, 2003. Nastaran Baradaran, Pedro C. Diniz, and Joonseok Park, “Extending the Applicability of Scalar Replacement to Multiple Induction Variables,” pp. 455-469, Languages and Compilers for High Performance Computing, 2004

  The present invention provides a semiconductor device design apparatus, design method, and design program that prevent a redundant memory access from remaining in an operation description and prevent an increase in the area of generated hardware to enable high-speed operation. It is to provide.

  According to an aspect of the semiconductor device design apparatus of the present invention, a storage unit storing an operation description in which a digital circuit operation including a plurality of array accesses and conditional statements is stored, and the operation description stored in the storage unit. The reuse relationship between the array accesses is analyzed based on the conditional statement, and the data reuse distance between the array accesses, the difference in the reuse distance between the array accesses, and the reuse of the array access occurs. The difference between the reuse distances and the specified value are compared in order from the longest reuse distance calculated by the analysis unit, and the analysis unit that calculates the condition to perform the difference. If the above, a description of a circular buffer is added to the behavioral description, and if the difference in reuse distance is less than the specified value, a first processing unit that adds a description of a shift register to the behavioral description; Above The array access in the operation description is replaced with the access to the temporary variable corresponding to the input / output end of the circular buffer or the access to the temporary variable corresponding to the input / output end of the shift register. And a second processing unit for generating a behavioral description by adding a conditional statement.

The figure which shows an example of operation | movement description. The figure which shows the example of the reuse graph corresponding to the action description shown in FIG. The figure which shows an example of the operation | movement description optimized by the existing method. The block diagram which shows an example of the optimization apparatus of the behavioral description to which this embodiment is applied. The block diagram which shows the function of the control part and memory | storage device which are shown in FIG. The flowchart which shows operation | movement of this embodiment. The figure which shows the example of the reuse graph corresponding to the action description of this embodiment. The figure which shows the analysis result containing the reuse conditions of this embodiment. The figure which shows the generation | occurrence | production state of the reuse which concerns on this embodiment. The figure which shows an example of the operation | movement description in the middle of the process by this embodiment. The figure which shows an example of the optimized operation | movement description by this embodiment. The figure which shows an example of the circuit produced | generated by the existing method. The figure which shows an example of the circuit produced | generated by this embodiment. The figure which shows an example of the operation | movement description in connection with this embodiment when the number of loops is a parameter. The figure which shows the analysis result containing the reuse condition in the case of the example shown in FIG. The figure which shows the generation | occurrence | production state of the reuse in the case of the example shown in FIG. The figure which shows an example of the optimized behavioral description in the case of the example shown in FIG. The figure which shows an example of the circuit produced | generated based on the optimized behavioral description.

  As described above, when the hardware is automatically generated from the behavioral description using high-level synthesis, the array access corresponds to the memory access. Since memory access takes a long time, it is effective to delete array access. The above-described scalar replace is a method of reducing the number of memory accesses by replacing the access to the memory with the access of the register. That is, the scalar replace is to reduce the simultaneous access from the same memory by holding the data read from the memory in the shift register and reusing the data held in the shift register.

  In order to perform the scalar replacement, it is necessary to store the data accessed from the memory in the shift register and analyze the opportunity to reuse the data stored in the shift register based on the dependency between the array accesses.

  The dependency between array accesses is considered to be dependent between array accesses when the same memory area is accessed multiple times. There are the following four types of dependence. Reading after reading (read after read: RAR), reading after writing (read after write: RAW), writing after reading (write after read: WAR), and writing after writing (write after write: WAW). Among these, there are three dependencies that can be reused: RAR, RAW, and WAW.

  For example, when an operation description written in the C language shown in FIG. 1 is input, array access A [y] [x], A [y] [x-2], A [0] [x], A [y -3] [x], the data of array access A [y] [x] is reused for A [y] [x-2], A [0] [x], A [y-3] [x] Are in a dependency relationship.

  For this behavioral description, the reuse relationship between array accesses is analyzed and the reuse distance is calculated. Using this analysis result, a shift register is inserted into the behavioral description, and array access is replaced with temporary variable access, that is, access to the shift register.

  Here, terms applied to the present embodiment are defined as follows.

  2A and 2B show reuse graphs corresponding to the behavioral description shown in FIG. A reuse graph is created by supplying a node of a reuse data source (hereinafter also referred to as a reuse source or a generator) or a node of a supply destination (hereinafter also referred to as a reuse destination) from each array access. A source node and a supply destination node are connected by an arrow called an edge. This edge is accompanied by a reuse vector.

  In the reuse graph shown in FIGS. 2A and 2B, each of the four circles indicates array access A [y] [x], A [y] [x-2], A [0] [x], A [y-3] [x] is represented, and the reuse relationship is represented by an edge. The root of the edge is a generator as a reuse source, and the tip of the edge is the reuse destination.

  In FIGS. 2A and 2B, the array access A [y] [x] is connected only to the edge directed outward from the array access A [y] [x], and the array access A [y] [x]. The edge facing is not connected. For this reason, array access A [y] [x] is a generator.

  The reuse vector <dy, dx> is added to the edge. The reuse vector <dy, dx> is configured by a difference between array access subscripts connected by edges. For example, the reuse vector of array access A [y] [x] and A [y] [x-2] is obtained as <0, 2>, and array access A [y] [x] and A [y] −3] The reuse vector with [x] is obtained as <3, 0>.

  The reuse vector <dy, dx> shown in FIG. 2A indicates how many times each array access is reused after the loop has been made to the generator. For example, in the case of the reuse vector <dy, dx> (in the case of a double loop), if the outer loop turns dy times and the inner loop turns dx times, it indicates that reuse occurs from the reuse source to the reuse destination.

  The reuse distance d shown in FIG. 2B represents how many times each array access is looped with respect to the generator and then reused in terms of the innermost loop count. The reuse distance d is calculated based on the reuse vector shown in FIG. That is, the reuse distance d is represented by “d = dy × j + dx”, where j is the reuse vector <dy, dx> and the number of inner loops. In the case of the reuse vector <3, 0> shown in FIG. 2A, the number of inner loops is 10 from FIG. Based on this, the reuse distance d is calculated to be 3 × 10 + 0 = 30. In the case of the reuse vector <0, 2>, 0 × 10 + 2 = 2. Even in the case of three or more loops, the reuse distance d can be calculated by the same method. For example, Non-Patent Document 3 discloses a calculation method.

  In addition, after the inner loop has been rotated 30 times, the data stored by the array access A [y] [x] is loaded by the array access A [y-3] [x]. Therefore, a shift register composed of 30 registers is prepared, data to be write-accessed by array access A [y] [x] is stored in the first register of the shift register, and each time the inner loop rotates, the shift register And the array access A [y-3] [x] is accessed to the shift register by replacing the read access of the array access A [y-3] [x] with the last register access of the shift register. Can be replaced.

  FIG. 3 shows a state in which array access is replaced with access to a shift register by an existing method. As shown in FIG. 3, the array accesses A [y] [x-2] and A [y-3] [x] shown in FIG. 1 are replaced with temporary variable accesses s2 and s30 (5th and 8th rows). Furthermore, as shown in lines 10 to 39, reuse of A [y] [x] to A [y-3] [x] and A [y] [x] to A [y ] Shift registers s1 to s30 are added for reuse in [x-2] (line 10 to line 39). That is, a total of 30 registers are added.

  In the case of the above existing method, since a description (s30 = s29, s29 = s28,...) For realizing the shift register by a flip-flop circuit is required, a shift register having a large area is introduced.

  Further, as shown by the dashed arrows in FIG. 2A, there is a limitation on the format of the reuse vector, for example, array access A [0] [x] in which a constant is included in a subscript that frequently appears in image processing (FIG. 3, line 7) cannot be deleted. As a result, memory access reduction is insufficient and performance improvement is insufficient.

  Furthermore, since there is array access A [0] [x] that cannot be deleted, the array A [y] [x] cannot be deleted, and it is necessary to leave a memory for storing the array A. Therefore, there is a problem that the circuit area increases and the operating frequency decreases.

  Therefore, in the present embodiment, the reuse relationship between the array accesses for the behavioral description is analyzed in consideration of the reuse occurrence condition. Further, based on the reuse distance, specifically, the difference in distance, array access is described as access to a shift register or access to a circular buffer. This makes it possible to further reduce array access, reduce the circuit area, and prevent a decrease in operating frequency.

(Embodiment)
Hereinafter, embodiments will be specifically described.

  In the present embodiment, optimization of integrated circuit design by optimizing behavioral descriptions will be described. The optimization of the behavioral description is a subordinate concept of the high-level synthesis, and the optimization of the behavioral description is used when generating the RTL description from the behavioral description configured by a programming language such as C language, as in the high-level synthesis. For example, it is widely applied to the design of image processing and audio signal processing circuits. However, this embodiment is not limited to optimizing behavioral descriptions, and can also be applied to high-level synthesis.

(Device configuration)
FIG. 4 shows an example of an operation description optimizing device to which the present embodiment is applied. The behavioral description optimizing device 10 is constituted by, for example, a computer, and this computer is constituted by, for example, an input device 12, an output device 13, a storage device 14, and a memory 15 connected to the control unit 11.

  The control unit 11 is a CPU (Central Processing Unit), for example, and executes a predetermined operation according to a program stored in the memory 15.

  The input device 12 is, for example, a keyboard for inputting information necessary for optimizing the operation description indicating the operation of the semiconductor integrated circuit and the operation description such as restrictions on the semiconductor integrated circuit.

  The output device 13 outputs the generated operation description and the like, and is configured by a printer, for example.

  The storage device 14 is a computer-readable storage medium such as a hard disk device or a flash memory. The storage device 14 stores, for example, a program necessary for the operation of the control unit 11, a program necessary for optimizing the operation description, or an operation description in C language, for example.

  The memory 15 is, for example, a RAM (Random Access Memory), and is loaded with a program and the like necessary for the operation of the control unit 11 read from the storage device 14.

  The storage device 14 need not be directly connected to the control unit 11 and may be connected via a network.

  FIG. 5 shows functions realized by the control unit 11 and the storage device 14 shown in FIG.

  The control unit 11 includes an analysis processing unit 11a, a first processing unit 11b, and a second processing unit 11c.

  Further, the storage device 14 stores an operation description 14a, reuse information 14b between array accesses generated in the course of the operation of the control unit 11, and an optimized operation description 14c.

(Operation)
FIG. 6 shows the operation of the control unit 11, and each function shown in FIG. 5 will be described with reference to FIG.

  First, the analysis processing unit 11a of the control unit 11 reads out the operation description 14a from the storage device 14, and considers the reuse relationship between the array accesses in consideration of the “if conditional statement” and the array access subscript in the operation description 14a. Analyze (S11). By this analysis, a reuse vector is generated in order to generate the reuse graph shown in FIGS.

  For example, in the case of the behavioral description shown in FIG. 1, as described above, array access includes A [y] [x] in the third row, A [y] [x-2] in the fourth row, and A in the sixth row. [0] [x], A [y-3] [x] in the seventh row, array access A [y] [x] as a generator, and array access A [y-3] as a reuse destination A reuse vector between [x], A [y] [x-2], and A [0] [x] is generated. At this time, the reuse relationship between the array accesses is examined in consideration of the “if conditional statement” in the behavioral description and the array access subscript.

  That is, the array access A [0] [x] indicates that A [0] [x] when the loop variable y is y = 1 or y = 2 from the description of the fifth and sixth lines shown in FIG. It can be seen that the value accessed by A [y] [x] is reused. Therefore, as shown in FIG. 7A, between the array access A [y] [x] and the array access A [0] [x], the reuse vector when y = 1 <1, 0. > And a reuse vector <2, 0> when y = 2 is generated.

  Further, the reuse vector <3, 0> between the array access A [y] [x] and the array access A [y-3] [x], and the array access A [y] [x] and the array access A The reuse vector <0, 2> between [y] and [x-2] is generated in the same manner.

  Next, the reuse distance between the array accesses shown in FIG. 7B and the difference in the reuse distance are calculated (S12). The difference in reuse distance will be described later.

  Thereafter, based on the behavioral description, the reuse occurrence conditions to be added to the arrows in the reuse graph, that is, y = 1, y = 2, etc. are calculated (S13).

  Here, the reuse occurrence condition refers to a condition that holds when reuse occurs in array access at the reuse destination. For example, in this embodiment, when the loop variable y = 1 or y = 2, A [0] [x] reuses the value accessed by A [y] [x]. The reuse condition is derived by analyzing the array access subscript included in the behavioral description and the “if conditional statement”.

  Next, a table including a reuse occurrence condition is generated based on the analysis result (S14). The table including the reuse occurrence condition is stored in the storage device 14 as, for example, reuse information 14b between array accesses.

  FIG. 8 shows a table including the reuse occurrence condition generated based on the analysis result, and FIG. 9 shows an example of the reuse occurrence graph generated based on the table including the reuse occurrence condition. Yes.

  In this table and graph, the arrows of the reuse graph of the array of interest (array A) are arranged from the top in ascending order of reuse distance, and access type, array access, reuse distance dn (n is , Natural number), variable name after array access replacement, reuse distance difference, and reuse occurrence condition.

  8 and 9, the first element of the access type is a generator, and each reuse destination is described below.

  The array access and the reuse distance correspond to each array access and the reuse distance of the reuse graph.

  The variable name after replacement is a variable name when array access as a reuse destination is replaced with a temporary variable, and this variable name is set to “s + reuse distance”, for example.

  The difference in reuse distance is the difference between the reuse distance of the target reuse destination and the reuse distance of the reuse destination immediately before the target reuse destination. In other words, it is the difference between two adjacent reuse distances in a plurality of reuse distances arranged in ascending order of reuse distance. The difference in the reuse distance is the size of the necessary shift register or circular buffer. That is, the reuse distance difference indicates the number of registers constituting the shift register or the number of elements of the memory constituting the circular buffer.

  As the reuse occurrence condition, y = 1 and y = 2 are set for the array access A [0] [x] analyzed using the reuse graph.

  Next, in the first processing unit 11b shown in FIG. 5, the shift register or the circular buffer is described based on the table including the reuse occurrence condition, the reuse occurrence graph, and the operation description stored in the storage device. Are added to the last part of the innermost loop (S15).

  Specifically, referring to the reuse occurrence graph shown in FIG. 9, descriptions of shift registers or circular buffers are added in order from the edge farthest from the generator. In other words, descriptions of shift registers or circular buffers to be accessed after replacement are added in order from the array access with the longest reuse distance. At this time, for example, a prescribed value is set for the difference in the reuse distance, and a description of the shift register or the circular buffer is added based on this prescribed value.

  As described above, the difference in reuse distance indicates the number of registers constituting the shift register or the number of elements of the memory constituting the circular buffer. When the difference in reuse distance is large, the circuit scale increases when the shift register is applied. Therefore, a prescribed value is set for the difference in reuse distance to prevent an increase in circuit scale, and array access is replaced with a shift register or a circular buffer.

  In the present embodiment, the specified value is set to “8”, for example. When the difference in the reuse distance is “8” or more, a configuration of a shift register results in a large-scale circuit, so that a circular buffer description is added. If it is less than “8”, the circuit scale does not increase so much even if it is constituted by a shift register, so a description of the shift register is added.

  In the case of the example illustrated in FIG. 8, the difference in the reuse distance of A [y] [x] → A [y] [x−2] is “2”, so that a shift register description is added. The number of registers constituting the shift register is set to a difference in reuse distance, in this case, “2”.

  Further, the reuse distance difference of A [y] [x−2] → A [0] [x] (when y = 1), A [0] [x] (when y = 1) → A [ The difference in reuse distance of 0] [x] (when y = 2), the difference in reuse distance of A [0] [x] (when y = 2) → A [y−3] [x] is , Both are “8” or more. For this reason, three circular buffers are added. The number of elements of the memory constituting the circular buffer is set to the reuse distance difference “8” “10” “10”, respectively.

  The variable names at the input and output ends of the shift register and the circular buffer are temporary variable names that are replaced with the reuse source and reuse destination of the arrows in the reuse graph based on the table including the reuse occurrence condition.

  Note that FIG. 10 is a description in which the description of the shift access and the circular buffer is only added at the stage of the first processing unit 11b, and the array access is not deleted.

  Next, in the second processing unit 11c shown in FIG. 5, the array access is replaced with a temporary variable access corresponding to the added shift register and the input / output end of the circular buffer, and a conditional statement is inserted. Then, an optimized behavior description is generated (S16).

  That is, array access is replaced with a temporary variable. Specifically, an array access that refers to a plurality of temporary variables, for example, a temporary variable connected to a plurality of temporary variables corresponding to A [0] [x] is prepared according to the reuse occurrence condition. The corresponding temporary variable is substituted according to the reuse occurrence condition. In this way, the behavioral description is replaced, and an optimized behavioral description is generated.

  FIG. 11 shows a state in which a description of a shift register and a circular buffer is added to the behavioral description shown in FIG. 1, array access is replaced with temporary variable access, and a conditional statement is inserted.

  In FIG. 11, the array access in the third, fourth, sixth and seventh rows shown in FIG. 1 is replaced with temporary variable access in the third to eleventh rows. In particular, the variable assigned in the “if conditional statement” in the seventh and eighth lines indicates a temporary variable newly added due to the reuse occurrence condition.

  Further, three circular buffers are described in the 13th to 24th lines, and shift registers are described in the 25th and 26th lines. Descriptions of these circular buffers and shift registers are inserted in order of increasing reuse distance from the generator.

  In the description of the three circular buffers buf2, buf1, and buf0, the 15th, 16th, 19th, 20th, 23rd, and 24th lines are pointers that indicate the access positions of the memory that constitutes the buffer. Descriptions of p2, p1, and p0 are added.

  FIG. 12 shows the structure of the shift register when the array access of the behavioral description shown in FIG. 1 is converted into temporary variable access by the existing scalar replace. In the case of an existing scalar replace, as described above, array access is replaced with access to a shift register. For this reason, as shown in FIG. 12, 30 registers s1 to s30 constituting the shift register are added. Since each of the registers s1 to s30 is composed of a flip-flop circuit, the circuit area increases.

  On the other hand, FIG. 13 shows a configuration when the array access of the behavioral description shown in FIG. 1 is converted into temporary variable access according to the present embodiment. In the case of this embodiment, it is composed of three circular buffers buf0, buf1, and buf2 and five registers s1, s2, s10, s20, and s30. Of these, the registers s1 and s2 constitute a shift register. Each of the circular buffers buf0, buf1, and buf2 is configured by, for example, a dual port memory. The circular buffer buf0 is composed of seven memory elements, and the circular buffers buf1 and buf2 are composed of nine memory elements.

  In the circular buffers buf <b> 0 to buf <b> 3, the value in the conditional expression of the if statement for restoring the number of memory elements to be prepared and the pointer indicating the memory access position is “reuse distance of corresponding edge−1”.

  Specifically, in the case of the buffer buf0, the reuse distance between A [y] [x-2] and A [0] [x], which are array accesses connected to the input / output ends, is “8”. Therefore, the number of memory elements in the buffer buf0 is “8-1 = 7”, and in the case of the buffers buf1 and 2, the reuse distance to the adjacent buffer is “10”. The number of “10-1 = 9”.

  In these circular buffers buf0, buf1, and buf2, the memory access positions are indicated by pointers p0, p1, and p2, respectively. The pointers p0, p1, and p2 correspond to array access subscripts. Data is read or written between the memory element designated by the pointers p0, p1, and p2 and the registers s2, s10, s20, and s30. That is, for example, in the buffer buf0, the data in the memory pointed to by the pointer p0 is read into the register s10, and then the data in the register s2 is written into the memory pointed to by the pointer p0. The pointer p0 is then incremented to point to the next memory element. The same operation is executed in the next loop, and the pointer p0 is incremented. When the pointer p0 indicates up to the last memory element, the pointer p0 returns to the top memory element specified in the first loop. Thereafter, in the next loop, the data held in the first memory element designated by the first loop is read to the register s10. The data held in the register s10 is data written from s2 in the first loop. That is, the data held in the first memory element in the first loop is held in the circular buffer buf0 for the set number of loops and then read out to the register s10. Can be obtained.

  A circular buffer constituted by a memory can significantly reduce a circuit area as compared with a shift register constituted by a flip-flop circuit.

  The operation description optimized as described above is output from the second processing unit 11c constituting the control unit 11, and stored in the storage device 14 as, for example, the optimized operation description 14c.

  The above example is a case where the memory realizing the circular buffer is an asynchronous memory. When the circular buffer is realized by a synchronous memory, the “reuse distance” is equal to the number of elements of the circular buffer, similarly to the shift register. In that case, it is necessary to slightly modify the output code.

(Effect of embodiment)
According to the above embodiment, the reuse relationship between array accesses is analyzed in consideration of the reuse occurrence condition described in the “if conditional statement” included in the behavior description, and the reuse distance between each array access is small. Calculates the difference between two adjacent reuse distances in order, and creates a table and graph that sets the variable name after each array access is replaced with temporary variable access, and the conditions for occurrence of reuse. doing. Therefore, it is possible to strictly analyze the array access reuse relationship.

  Furthermore, a prescribed value is set for the difference in reuse distance, and based on the above graph, the reuse distance difference is compared with the prescribed value in order from the array access where the reuse distance is farthest from the generator. When the difference is greater than or equal to the specified value, the array description is replaced with a circular buffer constituted by a memory. When the difference in reuse distance is less than the specified value, the operation description is optimized by replacing with a shift register. Since the circular buffer configured by the memory has a smaller circuit scale than the shift register, it is possible to prevent an increase in the area of the generated hardware.

  In addition, since the reuse relationship of array access is strictly analyzed, redundant array access can be further deleted, and high-speed operation is possible.

  In particular, in the image processing technology, array access including a constant in a subscript, for example, description such as A [0] [x] is frequently used. This description corresponds to, for example, processing of the edge portion of the image in image processing.

  When a known scalar replace is executed for such a behavioral description including array access, the array access cannot be sufficiently deleted, the performance improvement becomes insufficient, and it is necessary to leave a memory for storing the array A. Becomes large.

  On the other hand, in the case of this embodiment, it is possible to delete an array access whose subscript includes a constant. For this reason, it is possible to reduce the memory for storing the array, and to achieve a marked improvement in performance.

  When the circular buffer is realized by a synchronous memory, instead of “access to a temporary variable corresponding to the input / output end of the circular buffer”, “access to an array (buf2, buf1, etc.) corresponding to the circular buffer” It is also possible to make it. In this case, the number of elements in the circular buffer increases by one, but it is possible to reduce one each of registers (s30, s20, etc.).

  In addition, the first processing unit compares the difference in reuse distance with the specified value, and based on the comparison result, the description of the circular buffer or shift register is added to the operation description. However, the present invention is not limited to this. For example, it is also possible to determine a circular buffer or a shift register by providing a table that preliminarily defines the correspondence between the reuse distance difference and the circular buffer and the shift register, and subtracting the table based on the reuse distance difference.

(When the number of loops is not a constant but a parameter)
Furthermore, in the case of this embodiment, even when the number of loops in the behavioral description is not a constant, but is a parameter such as N or M, it is possible to easily and efficiently reduce array access. However, the maximum values of N and M are determined.

  For example, in the behavioral description shown in FIG. 14, the number of loops is described as the parameter “N” in the first and second lines. When the existing scalar replacement technique is applied to this behavioral description, a multiplexer having a large number of inputs corresponding to the parameter N is mounted. In other words, in this case, there is provided a shift register including a number of registers corresponding to the assumed maximum number of loops. In order to read data from an arbitrary register of this shift register according to the number of loops, a large-sized multiplexer having a large number of input terminals is arranged, and many input terminals of this multiplexer are connected to any register of the shift register. For this reason, the circuit scale increases.

  On the other hand, in this embodiment, in steps S11 to S14 shown in FIG. 6, the reuse distance between array accesses and the difference in reuse distance are considered in consideration of the “if conditional statement” in the behavioral description shown in FIG. And the reuse occurrence condition are calculated, and a table including the reuse condition shown in FIG. 15 is created.

That is, as shown in FIG. 15, the reuse distance d3 corresponding to the reuse condition “y = 1” of the array access A [0] [x] is “N” and the array access A [0] [x] is reused. The reuse distance d4 corresponding to the use condition “y = 2” is calculated as “2 ^* N”, and the reuse distance d5 corresponding to the array access A [y−3] [x] is calculated as “3 ^* N”. The difference between the reuse distance and the reuse distance is calculated as “d2−d1 = 2”, “d3−d2 = N−2”, “d4−d3 = N”, and “d5−d4 = N”.

  The variable names after replacement are array access A [y] [x], array access A [y] [x-2], array access A [0] [x], array access A [0] [x]. Corresponding to each of the array accesses A [y-3] [x], “s0”, “s2”, “s_N”, “s_2N”, and “s_3N” are set.

  Next, a reuse occurrence graph shown in FIG. 16 is generated based on the created table. Based on each arrow described in this graph, a shift register or a circular buffer is added in order from the arrow farthest from the generator (S15).

  Specifically, a description of a shift register or a circular buffer is added based on the difference in reuse distance and a specified value.

  For example, when “8” is set as the specified value, when the difference in reuse distance is “8” or more, a description of a circular buffer is added, and when the difference in reuse distance is less than “8”, shift A register description is added. However, when a shift register and a circular buffer are added, the maximum value of N is substituted for “N” appearing in the difference in reuse distance and compared with the specified value.

  Thereafter, access to the shift register and the circular buffer is replaced with temporary variable access, and a conditional statement is inserted to generate an optimized behavior description (S16).

  FIG. 17 shows a state in which access to the shift register and the circular buffer is replaced with temporary variable access and a conditional statement is inserted in the behavioral description shown in FIG.

  In FIG. 17, the array access in the third row, the fourth row, the sixth row, and the seventh row in FIG. 14 is replaced with the temporary variable access in the third row to the eleventh row. Three circular buffers are described in the lines, and shift registers are described in the 25th and 26th lines.

  FIG. 18 shows the configuration of the shift register when the array access of the behavioral description shown in FIG. 14 is converted into the temporary variable access by the scalar replace of this embodiment. In the case of this embodiment, it is composed of three circular buffers buf0, buf1, and buf2 and five registers s1, s2, s_N, s_2N, and s_3N. Of these, the registers s1 and s2 constitute a shift register. The circular buffers buf0, buf1, buf2 are configured by, for example, a dual port memory.

  As described above, the number of memory elements constituting the circular buffers buf0, buf1, and buf2 is “reuse distance of corresponding edge−1”. For example, when the maximum value of N is 10, the circular buffer buf0 is composed of N-3 = 7 memory elements, and the circular buffers buf1 and buf2 are composed of N-1 = 9 memory elements. The storage addresses of the circular buffers buf0, buf1, and buf2 are designated by pointers p0, p1, and p2, respectively. This pointer corresponds to a subscript for array access.

  As described above, according to this embodiment, even when the number of loops in the behavioral description is not a constant, but is a parameter such as N or M, array access can be reduced easily and efficiently. Is possible. Therefore, an increase in circuit scale can be prevented, and a circuit capable of high-speed operation can be realized.

  The reuse graph shown in FIGS. 7A and 7B, the table including the reuse occurrence condition shown in FIG. 8, and the creation of the reuse occurrence graph are arbitrary, and the calculated reuse distance and reuse are calculated. It is also possible to replace the array access with access to a shift register or a circular buffer based on the difference in distance and the specified value.

  In addition, the present invention is not limited to the above-described embodiments as they are, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Moreover, various inventions can be formed by appropriately combining a plurality of constituent elements disclosed in the above embodiments. For example, some components may be deleted from all the components shown in the embodiment. Furthermore, constituent elements over different embodiments may be appropriately combined.

  DESCRIPTION OF SYMBOLS 10 ... Operation description optimization apparatus, 11 ... Control part, 14 ... Memory | storage device, 11a ... Analysis process part, 11b ... 1st process part, 11c ... 2nd process part, 14a ... Action description, 14b ... Array access Reuse information between, 14c... Optimized operation description.

Claims (5)

A storage unit storing an operation description in which operations of a digital circuit including a plurality of array accesses and conditional statements are described;
From the behavioral description stored in the storage unit, the reuse relationship between the array accesses is analyzed based on the conditional statement, the data reuse distance between the array accesses, the reuse distance between the array accesses An analysis unit that calculates a difference and a condition under which the reuse of the array access occurs;
In order from the longest reuse distance calculated by the analysis unit, the difference in reuse distance is compared with a specified value, and if the difference in reuse distance is greater than or equal to the specified value, A first processing unit for adding a description of a circular buffer and adding a description of a shift register to the operation description when the difference in the reuse distance is less than the specified value;
The array access in the behavioral description is replaced with access to a temporary variable corresponding to the input / output end of the circular buffer or access to a temporary variable corresponding to the input / output end of the shift register. And a second processing unit for generating a behavioral description by adding a conditional statement to the description.   2. The design apparatus for a semiconductor device according to claim 1, wherein the difference in the reuse distance indicates the number of registers constituting the shift register or the number of elements of the memory constituting the circular buffer.   2. The semiconductor device design apparatus according to claim 1, wherein the circular buffer includes a plurality of dual port memories, and each of the plurality of dual port memories is designated by a pointer. Based on the operation description describing the operation of the digital circuit including a plurality of array accesses and conditional statements stored in the storage unit, the reuse relationship between the array accesses is analyzed based on the conditional statements, and the re-use between the array accesses is analyzed. Calculating a use distance, a difference in the reuse distance between the array accesses, and a condition under which the reuse of the array access occurs;
In order from the longest reuse distance, the difference in reuse distance is compared with a specified value. If the difference in reuse distance is greater than or equal to the specified value, a description of a circular buffer is added to the behavioral description. If the difference in reuse distance is less than the specified value, add a shift register description to the operation description;
The array access in the behavioral description is replaced with access to a temporary variable corresponding to the input / output end of the circular buffer or access to a temporary variable corresponding to the input / output end of the shift register. A method for designing a semiconductor device, characterized by generating a behavioral description by adding a conditional statement to the description. Based on the operation description describing the operation of the digital circuit including a plurality of array accesses and conditional statements stored in the storage unit, the reuse relationship between the array accesses is analyzed based on the conditional statements, and the re-use between the array accesses is analyzed. Calculating a use distance, a difference in the reuse distance between the array accesses, and a condition under which the reuse of the array access occurs;
In order from the longest reuse distance, the difference in reuse distance is compared with a specified value. If the difference in reuse distance is greater than or equal to the specified value, a description of a circular buffer is added to the behavioral description. If the difference in reuse distance is less than the specified value, add a shift register description to the operation description;
The array access in the behavioral description is replaced with access to a temporary variable corresponding to the input / output end of the circular buffer or access to a temporary variable corresponding to the input / output end of the shift register. A design program for a semiconductor device, characterized by adding a conditional statement to a description and causing a computer to execute a process of generating an operation description.

Images