CN100428161C - Memory Automatic Layout Method for Storage Subsystem of Embedded Microprocessor - Google Patents

Abstract

The storage subsystem memory automatic layout method of embedded microprocessor is a storage subsystem memory automatic layout method applied to the embedded microprocessor in system chip design, and its steps are as follows: put the binary target program generated by the external ARMCC tool chain into Run in the off-chip synchronous DRAM, obtain the access records of the embedded microprocessor in the running process; divide the binary target program into a series of data nodes and instruction nodes according to the link information and the access records generated in the previous step, And generate the relational matrix that represents the priority relationship between nodes; Select the node that is put into the on-chip SRAM according to the priority level to run, and obtain the selected node list; According to the selected node list, obtain a new binary target program; put the new The part corresponding to the node in the selected node list in the binary target program is put into the on-chip static random access memory to run.

Description

Memory Automatic Layout Method for Storage Subsystem of Embedded Microprocessor

technical field

The invention relates to an automatic layout method for storage sub-system memory of an embedded microprocessor used in system chip design, and belongs to the field of embedded microprocessor design.

Background technique

The storage subsystem of a modern system chip is generally composed of three main parts: embedded microprocessor, on-chip memory, and off-chip memory. According to their physical location and organizational characteristics, each part has different effects on chip performance. On-chip memory is generally accessed Very fast on-chip SRAM, its address space and off-chip memory are separated from each other, but share the address and data bus; off-chip memory is usually an off-chip synchronous DRAM chip, compared with on-chip SRAM, it The access speed is very slow and unstable, and the access power consumption is large. With the continuous improvement of the design level of the system chip, the problem that the low reading speed of the off-chip memory does not match the high main frequency speed of the processor chip directly limits the improvement of the overall performance of the processor chip, resulting in the performance of the processor chip. Loss. In addition, the high power consumption of accessing off-chip memory also increases the power consumption of the processor chip.

Contents of the invention

Technical problem: The object of the present invention is to solve the problems in the above-mentioned prior art, provide a storage subsystem memory automatic layout method of an embedded microprocessor, realize the memory layout optimization of the storage subsystem, improve the performance of the storage subsystem and reduce its power consumption.

Technical scheme: In order to solve the technical problems existing in the prior art, the storage subsystem memory automatic layout method of the embedded microprocessor designed by the present invention is aimed at including the ARM7TDMI embedded microprocessor of ARM Company, on-chip static random access memory, and off-chip synchronous Storage subsystem for dynamic random access memory. The steps are as follows: a) the original binary target program generated by the external ARMCC tool chain is all put into the off-chip synchronous DRAM to run, and the access record of the ARM7TDMI embedded microprocessor to the off-chip synchronous DRAM is obtained in the running process; b ) According to the link information generated by the ARMCC tool chain and the access record generated by the previous step, the original binary target program is divided into a series of data nodes and instruction nodes, and generates a relationship matrix representing the priority relationship between nodes; c) selection Put the nodes running on the on-chip SRAM: arrange all the nodes according to the priority level, and select the node with the highest priority; taking into account the influence of the relationship matrix, repeat the above arrangement for the remaining nodes and selection, until the on-chip static random access memory can no longer be put into any node, and obtain the selected node list; d) modify the original binary target program according to the selected node list, and obtain a new binary target program; e) convert the new binary target program into The part corresponding to the nodes in the selected node list is put into the on-chip SRAM for operation.

The steps of dividing the original binary target program into data nodes and instruction nodes are as follows: a) symbol table rebuilding: the ARMCC tool chain (referring to the tool chain used to compile the ARM instruction set provided by ARM company) generated contains the symbol table The text file is converted into a new symbol table that can be recognized by the division process; b) DCD (DCD is a pseudo-instruction defined in ARM assembly language, used to initialize 32-bit data storage units, and also used in the compilation process Save constants and data, called DCD data) Data analysis: determine which are DCD data nodes and which are DCD instruction nodes in the original binary target program; c) Function division: according to the execution times of each part of the function and the number of jump instructions It is divided into various instruction nodes, that is, with the jump instruction in each function as the boundary, the function is divided into several instruction nodes, and finally all functions in the original binary target program are divided into a series of instruction nodes; d) function call analysis: analysis Each function call instruction in all instruction nodes preliminarily constructs the extended control flow graph of the entire original binary target program; e) global stack analysis: the new global data node obtained by encapsulating the global stack of the original binary target program, the global The size of the data node is 1.5 times the stack size obtained during the program running; f) Data access analysis: determine the relationship between each instruction node and the global data node, and complete the extended control flow graph of the original binary target program. Wherein, the data node includes two kinds: one is the original global data node of the binary target program, and the other is a new global data node obtained by encapsulating the global stack of the binary target program; the instruction node is A plurality of function basic blocks are formed by cutting the functions conforming to the capacity limit of the on-chip SRAM in the binary target program according to the internal jump instructions. While generating a series of data nodes and instruction nodes, a relationship matrix is generated to represent the change of the priorities of other nodes after one or more nodes are moved into the on-chip SRAM due to the interrelationship between the nodes.

The list of selected nodes is obtained by using the knapsack algorithm: firstly, arrange all the nodes according to the priority level, select the node with the highest priority and put it into the list of selected nodes; The nodes perform the arrangement and selection in the previous step repeatedly until no more nodes can be placed in the on-chip SRAM, that is, the list of selected nodes is obtained. As a standard for arranging and selecting the priority of each node, the ratio of the program execution time that can be reduced by placing the on-chip SRAM for each node to the size of the node can also be used for each node. The ratio of the power consumption that can be saved behind the memory to the node size, the larger the ratio, the higher the priority.

Beneficial effects: the memory automatic layout method of the storage subsystem of the embedded microprocessor of the present invention adopts the on-chip static random memory allocation algorithm considering the relationship between nodes to carry out the on-chip static random memory allocation, accurately analyzes the performance optimization effect of the program, and changes The memory layout of the program properly allocates the program and data of the calculation-intensive application to the off-chip synchronous DRAM and the on-chip SRAM to ensure that the program with the most calls and the longest calculation time is located in the on-chip SRAM, fully The on-chip static random access memory space is used to improve the performance of the storage subsystem, reduce the huge power consumption caused by reading the external memory, and realize the optimization of the memory layout of the storage subsystem of the embedded microprocessor.

The memory automatic layout method of the storage subsystem of the embedded microprocessor of the present invention can improve the performance of application programs such as MP3 decoding programs by 37%-52%. The table below shows a test comparison of the relevant applications:

Description of drawings

Figure 1 is a block diagram of the storage subsystem of the ARM7TDMI embedded microprocessor.

Fig. 2 is a working flow diagram of the present invention.

Figure 3 is the extended control flow graph of the application.

In the figure are: ARM7TDMI embedded microprocessor 1, on-chip static random access memory 2, off-chip synchronous dynamic random access memory 3, storage subsystem performance simulation module 4, program divider 5, SPM allocator (on-chip static random access memory allocator) 6 , Linker 7.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

Figure 1 is a block diagram of the storage subsystem of the ARM7TDMI embedded microprocessor. The storage subsystem includes ARM7TDMI embedded microprocessor 1, on-chip static random access memory 2, and off-chip synchronous dynamic random access memory 3, wherein, ARM7TDMI embedded microprocessor 1 and on-chip static random access memory 2 are connected through AMBA bus; off-chip synchronization The DRAM 3 and the ARM7TDMI embedded microprocessor 1 are indirectly connected through the external memory control interface, the ARM7TDMI embedded microprocessor 1 and the external memory control interface are connected through the AMBA bus, and the data interface of the off-chip synchronous DRAM 3 and the control interface are correspondingly connected to the data interface and the control interface of the external memory through the data bus and the control bus respectively.

Work flow of the present invention is as follows, referring to Fig. 2:

In the first step, all the binary target programs generated by the external ARMCC tool chain are put into the off-chip synchronous DRAM 3 to run, and the access records of the ARM7TDMI embedded microprocessor 1 to the off-chip synchronous DRAM 3 are obtained during the running process.

In the second step, the program divider 5 divides the binary target program into a series of data nodes and instruction nodes according to the link information generated by the ARMCC tool chain and the access records, and completes the statistics of the access information of each node to generate A relationship matrix describing the relationship between individual nodes.

In the third step, the SPM allocator (on-chip SRAM allocator) 6 adopts the knapsack algorithm to select some nodes that will be put into the on-chip SRAM 2 according to the access information and the relationship matrix of each node, and obtains a list of selected nodes: All the nodes of the node are arranged according to the priority level, and the node with the highest priority is selected; taking into account the influence of the relationship matrix, the above arrangement and selection are repeated for the remaining nodes until the on-chip SRAM can no longer be placed in any node , get the list of selected nodes.

In the 4th step, the linker 7 modifies the original binary target program according to the selected node list to obtain a new binary target program;

In the fifth step, in the new binary target program generated by the linker 7, the part corresponding to the node in the selected node list is put into the on-chip SRAM 2 during the initialization stage of the new binary target program operation, and the storage is completed. Subsystem memory automatic layout optimization process.

According to the present invention, the original binary target program generated by the external ARMCC tool chain is divided into data nodes and instruction nodes. A new symbol table that can be recognized by the process; b) DCD data analysis: determine which are DCD data nodes and which are DCD instruction nodes in the original binary target program; c) function division: according to the number of execution times and jumps of each part of the function The instruction divides it into each instruction node, that is, divides the function into several instruction nodes with the jump instruction in each function as the boundary, and finally divides all the functions in the original binary target program into a series of instruction nodes: the jump instruction makes the program The number of executions of each instruction in the program is not exactly the same. Putting the most executed instructions in the program into the on-chip memory will reduce more execution time. Here, the jump instruction includes the jump destination address in this instruction inside the function The previous jump back instruction, such as jumping from the v3 node in Figure 3 to the v2 node, and jumping to the forward jump instruction of several instructions after the destination address in the function, such as the v2 node in Figure 3 jumping to v5 node, but does not include jump instructions whose destination address is not inside the function, jump instructions include conditional jump instructions and unconditional jump instructions; d) function call analysis: analyze each function call instruction in all instruction nodes, and initially build The extended control flow graph of the entire original binary target program; e) Global stack analysis: the global stack of the original binary target program is encapsulated, and the new global data node is obtained. The size of the global data node is the stack obtained during the program running 1.5 times the size; f) Data access analysis: determine the relationship between each instruction node and the global data node, and complete the extended control flow graph of the original binary target program. Wherein, the data node includes two kinds, one is the original global data node of the original binary object program, and the other is a new global data node obtained by encapsulating the global stack of the original binary object program; the instruction node , is a plurality of functional basic blocks formed by cutting the functions in the original binary target program that meet the capacity limit of the on-chip SRAM 2 according to the internal jump instructions.

As an embodiment of the present invention, the priority standard for arranging and selecting each node is the ratio of the amount of program execution time that can be reduced to the size of the node after each node is put into the on-chip SRAM 2 for operation, and the ratio is greater. Larger has higher priority.

As another embodiment of the present invention, the priority standard for arranging and selecting each node is the ratio of the power consumption that can be saved to the size of the node after each node is put into the on-chip SRAM 2 for operation, and the greater the ratio Larger has higher priority.

The four key modules involved in the automatic layout method of the storage subsystem memory of the embedded microprocessor of the present invention are respectively introduced below.

1. Storage subsystem performance simulation module 4:

Use the simulation function provided by the ARMCC tool chain of ARM to design and write the storage subsystem performance simulation module of the embedded microprocessor, so that when the application program runs on this module, the access record of the application program to the storage subsystem can be obtained for subsequent steps .

2. Program divider 5:

In order to make full use of the compiling and optimizing ability of the ARMCC tool chain of ARM Company, the on-chip SRAM optimization technology of the present invention directly analyzes the binary target program file output after ARMCC linking, rather than the C language source code of the program. Comprehensively analyze all contents of a program, including functions, global data variables, and the global stack, by rebuilding the program's symbol table. Among them, all the functions in the program conforming to the size limit of the on-chip SRAM are cut into multiple basic blocks according to the internal jump instructions; the global stack of the program is encapsulated into a global data variable. Since the stack size of the program will change when it processes different inputs, in order to prevent stack overflow, the size of the data variable is 1.5 times the actual stack size used during the running of the program, and the global data variable of the original binary target program remains unchanged. Change. Finally, the program content sent to the SPM allocator (on-chip static random access memory allocator) 6 for selection includes global data variables and function basic blocks.

The program divider 5 divides the original binary target program output by the ARMCC tool chain into six steps: symbol table reconstruction, DCD data analysis, function division, function call analysis, global stack analysis and data access analysis. After the above six steps, the original binary target program is divided into a series of instruction nodes and data nodes. Among them, there are two types of data nodes, one is the original global data node of the original binary target program, and the other is to encapsulate the original binary target program The new global data node obtained from the global stack; the instruction node refers to a plurality of functions that meet the capacity limit of the on-chip SRAM 2 in the original binary target program and are cut according to its internal jump instructions basic block. For the convenience of the algorithm design and realization of follow-up SPM allocator (on-chip static random access memory allocator) 6, the present invention has set up a kind of extended control flow graph to describe these program contents and the relationship between them, among Fig. 3 V6 is data Nodes, other nodes are instruction nodes, except for the unconditional transfer relationship, the relationship between other nodes is illustrated in the figure: conditional transfer relationship, data access relationship, sequential execution relationship, and call relationship. Some ARM instructions have very strict restrictions on the address space, such as jump instructions and data load instructions. Usually, because the address jump range is too large, a jump instruction cannot jump between off-chip memory and on-chip memory. After the jump instruction in the off-chip memory is moved to the on-chip memory, it will be replaced by two instructions, resulting in an increase in the size of the node moved to the on-chip memory, thereby affecting program performance and power consumption. Therefore, it is necessary to analyze the influence of the node size and the impact on the program performance and power consumption after the relationship initiator node and the relationship receiver node of the five kinds of relationships between nodes are moved into the on-chip SRAM 1 respectively. The present invention uses a relationship matrix to represent the influence of the relationship between nodes on node size, program performance and power consumption, including a performance matrix TRM _ij , a power consumption matrix ERM _ij and a size matrix SRM _ij . Respectively, if and only when the node V _i is moved into the SPM, the impact of all relationships between the node V _j and V _i on the program execution time, the impact on power saving and the impact on the node size, expressed by the following formula:

${\mathrm{<span\; class="notranslate">\; TRM</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; type</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 5</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}}_{\mathrm{<span\; class="notranslate">\; start</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; type</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}}_{\mathrm{<span\; class="notranslate">\; end</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; type</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; ERM</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; type</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 5</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&Delta;E</span>}}_{\mathrm{<span\; class="notranslate">\; start</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; type</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; \&Delta;E</span>}}_{\mathrm{<span\; class="notranslate">\; end</span>}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; type</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; SRM</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; type</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 5</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; \&Delta;S</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; type</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

In the formula, R _type (i, j) represents the five relationships between nodes, ΔT _start represents the change of program execution time after the relationship initiator node moves into the on-chip SRAM (1), and ΔT _end represents the relationship receiver node moves into the on-chip SRAM The change of program execution time after random access memory (1), ΔE _start represents the change of power consumption saved after the relationship initiator node is moved into the on-chip SRAM (1), and ΔE _end represents the relationship receiver node is moved into the on-chip SRAM (1 ), ΔS represents the change in the size of the node after the node is moved into the on-chip SRAM (1).

3. SPM allocator (on-chip static random memory allocator) 6:

The allocator adopts the improved knapsack algorithm considering the relationship between nodes, arranges and selects all nodes, and obtains a list of nodes that will be put into the on-chip SRAM 2. The steps are as follows: a. Rank high and low, select the node with the highest priority and put it into the selected node list; b, taking into account the influence of the relationship matrix, repeatedly carry out the arrangement and selection of the previous step for the remaining nodes until the on-chip SRAM 2 can no longer be placed Enter any node to get the list of selected nodes. The standard for selecting nodes to be placed in the on-chip SRAM 2 may be the size of the performance gain that each node can obtain after being placed in the on-chip SRAM 2, or the amount that each node can save after being placed in the on-chip SRAM 2 The size of the power consumption, the higher the priority of the performance benefit, or the higher the priority of saving more power consumption.

4. Linker 7:

After obtaining the node list selected to be moved into the on-chip SRAM under the capacity of the current on-chip SRAM 2, relink all nodes in the program by the linker 7 written in C language, and automatically generate a new binary file, which includes Three parts: initialization part, off-chip synchronous DRAM part and on-chip static random access memory part, among them, the off-chip synchronous DRAM part is to modify the jump instruction according to the node moving situation of the original binary target program, the initialization part and the on-chip The SRAM part is newly added by the linker, and the on-chip SRAM part also modifies the jump instruction according to the node moving situation. The initialization part copies the on-chip SRAM part to the real on-chip SRAM 2 storage space, and then Jump to the first address of the main function of the original program. If the first node of the main function is selected and moved into the on-chip SRAM 2, the initialization part will directly jump to the corresponding position of the on-chip SRAM 2. The new binary object program starts execution from the initialization section.

Claims (3)

1, a storage subsystem internal memory automatic layout method of a kind of embedded microprocessor, this storage subsystem comprises ARM7TDMI embedded microprocessor (1), on-chip static random access memory (2), off-chip synchronous dynamic random access memory (3), its It is characterized in that the memory automatic layout method comprises the following steps: 1a) Put the original binary target program generated by the ARMCC tool chain into the off-chip synchronous DRAM (3) to run, and obtain the ARM7TDMI embedded microprocessor (1) to the off-chip synchronous DRAM (3) during operation. access records; 1b) According to the link information generated by the ARMCC tool chain and the access records described in step 1a), the original binary target program is divided into a series of data nodes and instruction nodes, and generates a relationship matrix representing the priority relationship between nodes; 1c) Select the node to run on the on-chip SRAM (2): 1c1) Arranging all the nodes according to the priority level, and selecting the node with the highest priority; 1c2) For the influence of the relationship matrix described in step 1b), repeatedly carry out the arrangement and selection described in step 1c1) for the remaining nodes until the on-chip SRAM (2) can no longer be placed into any node, and a list of selected nodes is obtained; 1d) modifying the original binary target program according to the selected node list to obtain a new binary target program; 1e) putting the part corresponding to the node in the selected node list in the new binary target program into the on-chip SRAM (2); The steps of dividing the original binary target program into data nodes and instruction nodes are as follows: 2a) Symbol table reconstruction: convert the text file containing the symbol table generated by the ARMCC tool chain into a new symbol table that can be recognized by the division process; 2b) DCD data analysis: determine which are DCD data nodes and which are DCD instruction nodes in the original binary target program; 2c) Function division: According to the number of execution times of each part of the function and the jump instruction, it is divided into each instruction node, that is, the function is divided into several instruction nodes with the jump instruction in each function as the boundary, and finally the original binary All functions in the target program are divided into a series of instruction nodes; 2d) Function call analysis: analyze each function call instruction in all instruction nodes, and initially construct the extended control flow graph of the entire original binary target program; 2e) Global stack analysis: Encapsulate the global stack of the original binary target program to obtain a new global data node. The size of the global data node is 1.5 times the stack size obtained by statistics during the running of the program; 2f) Data access analysis: determine the relationship between each instruction node and the global data node, and complete the extended control flow graph of the original binary target program. 2. The storage subsystem memory automatic layout method of an embedded microprocessor according to claim 1, wherein said priority is the program execution that can be reduced after each node is put into the on-chip SRAM (2) The ratio of time to node size, the larger the ratio, the higher the priority. 3. The storage subsystem memory automatic layout method of an embedded microprocessor according to claim 1, wherein said priority is the power consumption that can be saved after each node is put into the on-chip SRAM (2) The ratio of size to node size, the larger the ratio, the higher the priority.

Images