Execution method of control flow program, development method of data flow program, data processing system, program execution method and device and control instruction of data processing system, computer-readable recording medium, development method and conversion method of computer-loadable program

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Technical field to which the invention belongs]

The present invention relates to a multiprocessor computer system, and more particularly to data-driven processing of a computer program using the multiprocessor computer system.

【0002】

[Conventional technology]

A multiprocessor computer system includes two or more processors used to execute various instructions of a computer program. A special instruction set may be executed by a single processor while another processor is executing an unrelated instruction set.

【0003】

High-speed computer systems, such as multiprocessor systems, have stimulated rapid advances in new ways of conducting scientific research. A wide range of classical branches and leaves of theoretical and experimental sciences have been linked by computer-based science. Computer scientists use supercomputers to simulate phenomena that are theoretically too complex to be reliable, or that are too dangerous or expensive to reproduce in the laboratory. The success of computer-based science has rapidly increased the need for supercomputer resources in recent years.

【0004】

During this time, multiprocessor computer systems, also known as parallel computers, have evolved from laboratory lab equipment to become the everyday tool of scientists who use computers and need the best of computer resources to solve problems. It was. Several factors have stimulated this evolution. It's not just that the speed of light and heat consumption efficiency impose physical limits on the speed of a single processor. Part of this is that the cost of modern single-processor computers is growing faster than their capacity. And if the required computing power is found in existing resources without new purchases, the price-to-performance ratio becomes more desirable. This has increased the chances that workstation networks, originally purchased for minor chores, will be used as "SCAN" (an abbreviation for midnight supercomputer) by using workstation networks as parallel computers. This plan proved to work so well that the cost-effectiveness of personal workstations grew rapidly, so the workstation network was purchased exclusively for parallel jobs running on relatively fast supercomputers. It has come to be. Thus, considering both peak performance and price-to-performance ratio, it is driving large-scale computer computing to move toward parallel processing. Despite these advances, parallel computers have not been widely adopted.

【0005】

The biggest obstacle to the adoption of parallel computer computing and its economic and performance benefits is the problem of software inadequacy. Those who develop programs that run parallel algorithms for critical computer-powered scientific problems will find that their current software environment facilitates the smooth use of very high-performance, available, and cost-effective hardware. You will find that it has not been reached, but rather an obstacle to it. This is because computer programmers generally follow a "control flow" model when developing programs, including programs executed by multiprocessor computer systems. According to this model, the computer is controlled by a program counter to execute the instructions of the program in sequence (that is, execute the first instruction to the last instruction in series). This method simplifies the program development process, but is inherently slow.

【0006】

For example, when a program counter reaches a particular instruction in a program that requires the result of another instruction or instruction set, that particular instruction is said to be "dependent" on the result, until the processor makes the result available. The instruction cannot be executed. Furthermore, when a program developed under the control flow model is executed on a parallel processing computer, these dependencies result in wasted resources. For example, a first processor that executes a set of instructions in a control flow program may be a second processor with respect to another set of instructions that requires a result for the first processor to execute that set of instructions. May have to wait until it completes execution. This wait time can be said to be an unacceptable waste of computer resources in that at least one computer consisting of two processors does not run for the entire duration of its program.

【0007】

For the application of effective parallelism in programs, scientists have suggested using a "data flow" model instead of a control flow model. The basic concept of this data flow model is that instructions can be executed whenever the required operands are available. Therefore, a program counter is not required for data-driven computer computation. Instruction initiation depends on the availability of data, but not on the physical position of the instruction in the program. In other words, the instructions in the program are not ordered. Execution simply follows data dependency constraints.

【0008】

A data-driven computer computing program is represented by a data flow graph. An example of a data flow graph for the calculation represented by Equation 1 is shown in Figure 1.

【0009】

[Number 1]

<img file="JP2000285084A_D0001.tif" />For example, when x is 5 and y is 3, the result z is 16. As shown, z depends on the sum and the results of x and y. The data flow graph is a directed acyclic graph (DAG) whose nodes correspond to operators and whose arcs serve as pointers to data progression. The graph reveals order constraints (ie, constraints on data dependencies).

【0010】

For example, on a typical computer, (i) when a program is compiled for better resource utilization and code optimization, (ii) collaborative arithmetic logic for faster system throughput. Program analysis is often done at run time to clarify the arithmetic operation. For example, assume the instruction sequence shown in Table 1.

【0011】

[table 1]

<img file="JP2000285084A_D0002.tif" />【0012】

When executing the instructions in a serial computing system (eg, a single processor system), the five computational sequences shown in Table 2 are allowed to ensure the integrity of the results.

【0013】

[Table 2]

<img file="JP2000285084A_D0003.tif" />【0014】

For example, the first instruction must be executed first, while the second or third instruction can be executed second. This is because the result of the first instruction is required by the second and third instructions, but the second or third instruction does not require the result of the other instructions. The rest of each sequence follows the simple rule of not executing an instruction until an operand (or input) is available.

【0015】

In a multiprocessor computer system that includes two processors, it is possible to perform the above six operations in four (but not six) steps. It consists of calculation steps 1 by the first processor, then calculations steps 2 and 3 performed simultaneously by both processors, then calculation steps 4 and 5 performed simultaneously by both processors, and finally calculation performed by either processor. Step 6 This reduces execution time, which is a clear improvement over the single-processor approach.

【0016】

When the data flow is used as a means of parallel processing, the system processing can be made parallel processing to the maximum extent in this way. However, most source code takes the form of control forms that are difficult and unsuitable for efficiently parallelizing all types of problems.

【0017】

Therefore, to make it easier for developers to develop data flow programs, and to easily convert existing control flow programs into data flow programs for running on multiprocessor computer systems. Is required to do. Further, there is also a demand for a technique for optimizing the operation of a data flow program in a multiprocessor computer system by inputting various required specifications.

【0018】

The present invention allows a developer to easily develop a data flow program and execute a control flow program that can easily convert an existing control flow program into a data flow program for execution in a multiprocessor computer system. Method, data flow program development method, data processing system, program execution method, program execution device, computer-readable recording medium that stores control commands of the data processing system, computer-implementable program development method, computer-implementable The purpose is to provide a method of converting a program. In addition, a control flow program execution method, a data flow program development method, a data processing system, a program execution method, which can optimize the operation of a data flow program in a multiprocessor computer system by inputting various required specifications, It is an object of the present invention to provide a program execution device, a computer-readable recording medium that stores control instructions of a data processing system, a method for developing a computer-implementable program, and a computer-impleable program conversion method.

【0019】

[Means for solving problems]

The methods, systems and products according to the present invention overcome the drawbacks of existing systems by allowing developers to easily convert control flow programs into data flow methods and develop new programs using data flow models. It is a thing. The gist of the present invention is clear from the system and the product according to the embodiment, but the program development process includes a process of defining a memory area and dividing it into a plurality of blocks, and each block is a numerical set associated with a function. Is defined. When a block set is defined, each block of the set has a state corresponding to a specified part of the program, and the program transforms the numerical values that make up the block based on the function at run time. In addition, the dependencies between blocks are specified by the user. Each dependency shows the relationship between the two blocks and requires that the program part associated with one of the two blocks be executed before the program part associated with the other block. ..

【0020】

According to another gist of the present invention, the methods, systems and products according to embodiments execute data flow programs on a multiprocessor computer system. The program execution process consists of the process of selecting information in the queue that identifies the block consisting of the numerical set associated with the function of the program, and the execution of the program part associated with the selected block of the program part associated with other blocks. It includes a step of determining whether or not it depends on the execution result. Next, the program part associated with the selected block is executed, but the execution of the program part associated with the selected block does not depend on the execution result of the program part associated with the other block. It is done when it is decided. This selection and determination is repeated when it is determined that the execution of the program portion associated with the selected block depends on the execution result of the program portion associated with the other block.

【0021】

Further, according to another gist of the present invention, the methods, systems and products according to the embodiments allow the user to optimize the program development process by inputting various item specifications. This program development process includes a step of defining a memory area, a step of dividing the memory area into blocks, and a step of defining the element aspect of the block of the memory area. By using the code, the user can write the control flow program code to access the block. Further, in order to facilitate the user's specification of the dependency between blocks, a method for efficiently generating the dependency between block sets has been proposed. In addition, the method allows the user to group blocks for processing, if desired, and to use various parallel processing schemes.

【0022】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings. When the same or substantially the same member is referred to in the drawings and description, the same reference numerals are used as much as possible.

【0023】

Introduction The methods, systems and products according to the present invention allow developers to convert control flow programs into data flow programs and to develop new programs based on data flow models. Such methods, systems and products can also utilize development tools, including computer-to-human interfaces, to design and develop dataflow programs.

【0024】

A dataflow program developed according to the principles of the present invention is executed on a multiprocessor computer system using a dataflow model. The interface may be operated on a data processing system different from that used to execute the program. Alternatively, the interface may be operated on the system for program execution.

【0025】

One of the features of the data flow model according to the present invention is that operations are executed in parallel in blocks of a memory area. A block consists of a data set such as a sequence, a matrix, or other information. The plurality of blocks together constitute a memory area.

【0026】

Dataflow program development tools provide an interface that allows developers to define memory areas that contain data associated with the system. Here, the term "system" relates to physical, mathematical, and computer-calculated problems such as structural analysis of buildings and fluid flow rates of pipes. Usually, such a complex system requires a great deal of processing to solve many equations, and the result of one set of equations depends on the result of the other set of equations. For example, the fluid flowing through a pipe is slowed down by friction inside the pipe. The friction directly affects the speed of the fluid in contact with the inside of the pipe (defined by the equation of the first set) and indirectly affects other fluids in the pipe not in contact with the inside (defined by the same equation). However, it depends, perhaps, on the results of the equations in the first set). Thus, the effect of friction inside the pipe on the fluid in the pipe depends on its position in the pipe.

【0027】

After defining the region, the developer divides the region into blocks and for each block specifies the program code to execute for each block, in addition to the dependencies between that block and other blocks in the region. To do. Blocks with the same program code are said to share the same "state". They are generally run in parallel because they are independent of each other in terms of results. In the example fluid flow, the blocks associated with the fluid flowing inside the pipe share the same state (and thus have the same program code for execution), but this state (and code) does not. , Not in contact with the inside, but at least different from the state (and code) of the fluid in contact with the fluid. As you move to the center of the pipe, the state (and code) of each block associated with the fluid in the pipe changes, similarly reflecting the dependencies.

【0028】

Dependencies are represented by links between each of the dependent blocks and the dependent blocks. When the first block requires the result of the second block in order for the first block to work properly in the system, the block depends on the other blocks. This relationship may be viewed graphically with a directed acyclic graph. The program code and data determined in block units are associated with each node of the graph.

【0029】

The block is queued for processing on a multiprocessor computer system. In reality, the block itself cannot be queued. Rather, information that identifies each block, such as pointers, is queued. Blocks are queued or configured in a particular way, and the thread that executes the dataflow program is suitable for executing the corresponding program code at a given point in time while the dataflow program is being executed. You can select blocks. According to one implementation, blocks are queued according to the dependency information associated with each block.

【0030】

The developer can also specify the number of threads available to process the block. Each thread manages program counters and temporary memory as needed to execute the program code associated with the block. For example, a developer can specify one thread for one processor. Other configurations are possible according to the principles of the present invention.

【0031】

Each thread, in turn, selects a block from the queue and executes the program code specified by the developer for that block. As long as there are blocks in the queue, the thread will select them, if valid, and execute the appropriate program code. In addition, the queued blocks are selected for execution in a way that reflects the dependency information for each block. When a valid thread selects a queued block for execution, it first checks the block's dependency information (ie, links to other blocks), and if the selected block depends on the block. When the execution is complete, the thread can proceed with the execution of the program code of the selected block. Otherwise, the thread goes into a wait state until it starts executing the program code of the selected block. Instead, the thread selects the next valid block in the queue, if appropriate, based on priority, and inspects the corresponding block to determine the state with respect to the block on which it depends (ie, of the selected block). Complete the execution of all blocks it depends on so that the program code can be executed safely). This process continues until the thread completes the execution of the program code associated with every block in the queue.

【0032】

In addition, the user is given a way to add additional specifications to the program during the development process. With these specific items, the attributes of the elements in the block in the memory area can be specified, and the dependency between a plurality of block sets can be efficiently specified. In addition, the system delivers code called "macro", which allows the user to write control flow program code to access the elements of the block. In addition, the user can assign a block set to a distributed group that determines how the blocks are processed in parallel.

【0033】

The following description includes details about the design and development of the data flow program and the subsequent aspects of the execution phase. Data flow program definition process using regions and blocks At the beginning of the design and development process, the developer specifies a memory area and divides the area into multiple blocks. This is done with charts using the interface of the development tool. FIG. 2 shows an example of a memory area 100 containing 16 blocks arranged in a 4x4 matrix, and each block is identified by a row number and a column number. For example, the block in the upper left corner of the memory area 100 is labeled (1,1) indicating that it is installed in the first column of the first row, and the block in the lower right corner of the area 100 is installed in the lower right corner. A label (4,4) is attached to indicate that the product is used. All of the remaining 14 blocks will be labeled according to similar labeling promises. As described, each block consists of a data set, which is a matrix or array of numbers or information, processed according to program code.

【0034】

After defining the memory area and dividing it into blocks, the developer specifies the state of each block. As explained, the state of the block corresponds to the program code that the developer has assigned to the block, and the developer intends to have the multiprocessor computer system process the block data using the specified program code. Means that The interface provides the developer with a window or other means for assigning program code to the block. The development tool associates the code with the block.

【0035】

In the illustrated region 100, the block groups 100a of the labels (1,1), (2,1), (3,1) and (4,1) share the same state and the labels (1,2), ( The block groups 100b of 1,3) and (1,4) share the same state and are labeled (2,2), (2,3), (2,4), (3,2), (3, The block groups 100c of 3), (3,4), (4,2), (4,3) and (4,4) share the same state. In Figure 2, the three different states are represented by applying different shading (or fill) to the blocks in each group.

【0036】

Area 100 and its blocks appear to be uniform in size, but in practice memory areas and blocks have different shapes and sizes. For example, the memory area 100 consists of 16 blocks of a 4x4 matrix, and although not shown in the figure, each block may have an 8x8 matrix. Various memory areas may consist of a matrix of 4x3 blocks, and each block may consist of a matrix of 3x2 data.

【0037】

The developer then specifies the dependencies between the blocks. Further, a dependency is defined as a relationship in which one block depends on the result or final state of another block during program execution. In other words, one block must be processed before the other dependent blocks are processed. 3A and 3B show examples of multiple dependencies using region 100 of FIG. As shown in FIG. 3A, the blocks labeled (1,2), (1,3) and (1,4) are labeled (1,1), (2,1), (3,4, respectively). It depends on the blocks labeled 1) and (4,1). This means that all blocks labeled (1,1), (2,1), (3,1) and (4,1) are (1,2), (1,3) and ( This means that it must be processed before the blocks labeled 1,4).

【0038】

Similarly, FIG. 3B shows the blocks labeled (1,2), (1,3) and (1,4) and (2,2), (2,3), (2,4). , (3,2), (3,3), (3,4), (4,2), (4,3) and (4,4) Dependencies with the labeled blocks Shown. As shown, the block of label (1,2) must be processed before the block of label (2,2), (3,2), (4,2) in the same column and label (1). The block of, 3) must be processed before the blocks of labels (2,3), (3,3), (4,3) in the same column, and the block of label (1,4) , Must be processed before blocks of labels (2,4), (3,4), (4,4) in the same column. The figure simply shows an example of the dependency configuration, and the developer may choose another configuration.

【0039】

When completing a chart showing dependencies, it would be convenient if it could be visually viewed using the user interface and completed. FIG. 4 is a directed acyclic graph illustrating the dependencies in FIGS. 3A and 3B. The directed acyclic graph shown in FIG. 4 visually shows that all the outputs of the blocks sharing the first state are required for each processing of the blocks sharing the second state. Second, each of the blocks that share the second state must be processed before each of the three groups of three blocks that share the third state. Blocks may be ordered using such a graph to process according to the principles of the invention (discussed below).

【0040】

Data flow programming tool Computer architecture FIG. 5 shows a typical example of a data processing system 500 suitable for carrying out the method according to the present invention and implementing the system according to the present invention. The data processing system 500 includes a computer system 510 connected to a network 570 such as a local area network, a wide area network or the Internet.

【0041】

The computer system 510 includes a main memory 520, a sub storage device 530, a central processing unit (CPU) 540, an input device 550, and an image display device 560. The main memory 520 holds the data flow program development tool 522 and the program 524. Dataflow program development tool 522 provides an interface for designing and developing dataflow programs, including programs that use control flow program code. Using the tool with the display device 560, the developer can design a memory area as shown in area 100 of FIG. 2 and divide the area into blocks having corresponding states. In addition, the tool allows developers to write program code to process each block using a multiprocessor computer system (see Figure 7).

【0042】

Program 524 presents a data flow program designed according to the present invention, for example using tool 522. The program 524 consists of a memory area, blocks of the area, program code associated with each block, and information for identifying dependencies between blocks.

【0043】

An example of an embodiment is stored in memory 520, but for those skilled in the art, all or part of the systems and methods according to the present invention are stored in other computer-readable media such as sub-storage devices. It is self-evident that it may be read from it. For example, hard disks, floppy (registered trademark) disks, and CD-ROMs, carriers received from networks such as the Internet, or other types of ROM or RAM fall under the sub-storage device. Also, specific components of the data processing system 500 will be shown, but it will be obvious to those skilled in the art that a data processing system suitable for the methods and systems according to the invention may include additional or different components. is there.

【0044】

Process FIG. 6 is a flow chart of process 600 executed by the developer to write a program that uses the data flow model. This process may be performed by the tool 522 in the manner according to the invention. Tool 522 has a user interface and related functions, and provides an environment for software developers to write programs that use a data flow model.

【0045】

When the developer starts running Tool 522, it displays the various charts that the developer needs to write the dataflow program. The tool first displays the charts that the developer uses to define the memory area (step 610). Using tool 522, the developer divides the area into blocks (step 620).

【0046】

As long as there are blocks in the area to be processed (step 630), the developer selects the block (step 640) and other blocks that affect the final state of the selected block (in other words, the block on which the selected block depends). Is identified (step 650), and the program code for each block, eg, a portion of an existing control flow program, is specified (step 660). This process involves transforming this existing control flow program to run on a multiprocessor computer system using a dataflow configuration, but for those skilled in the art, to run on a multiprocessor computer system. It is self-evident that the tool 522 may be used to develop a new data flow program.

【0047】

After all the blocks have been processed (steps 640-660), the developer establishes the dependencies between the blocks by associating the blocks with each other on the image (step 670), and tool 522 corresponds to the link. The visual information is used to generate and store the data to be generated. The block is logically queued for processing on a multiprocessor computer system (step 680). Tool 522 uses the dependency / link information to queue the blocks in the order appropriate for processing. For example, any block on which a particular block depends is placed before that particular block in that queue. For the examples of FIGS. 2-4, the blocks are queued in the manner shown in FIG. Specifically, the blocks sharing the first state, that is, (1,1), (2,1), (3,1) and (4,1) are the blocks having the second state, that is, , (1,2), (1,3), and blocks that are placed before (1,4) and share a third state, namely (2,2), (2,3), ( 2,4), (3,2), (3,3), (3,4), (4,2), (4,3) and (4,4) follow.

【0048】

Executing a multiprocessor program As described, according to the present invention, a data flow program is executed on a multiprocessor computer system. There are many configurations of such a multiprocessor computer system, and Fig. 8 shows an example. For example, in a tightly coupled configuration, multiple processors are all placed in the same physical box. In other loosely coupled configurations, the system consists of multiple computers on the network, each computer having a separate processor.

【0049】

Multiprocessor computer system As shown in FIG. 8, the multiprocessor computer system 810 is connected to the network interface 820. The interface allows developers to move dataflow programs from the development tool environment (see Figure 5), in order to run them on the multiprocessor computer system 810. Alternatively, the dataflow program development process according to the principles of the present invention may be run on system 810, which is also used to run the program. According to this alternative method, it is not necessary to move the program from the development system to a separately provided program execution system.

【0050】

The multiprocessor computer 810 consists of one shared memory 830 and a plurality of processors 840a, 840b, ... 840n. Regarding the execution of the data flow program developed according to the present invention, the number and type of processors are not particularly limited. For example, an HPC server configured with a plurality of processors may be used. The HPC server is a product of Sun Microsystems, Inc. The processes run independently on each processor and share memory 830. The process referred to here may be a thread that controls the execution of the program code associated with the block of the data flow program developed using the tool 522.

【0051】

process The operation of the data flow program according to the present invention will be described with reference to Process 900 in FIG. Multiple threads are used to process various components of a dataflow program. The number of threads is not important, and the developer may determine the number of threads. For example, there may be one thread per processor. The number of threads may also be determined based on the number of processors available to the system and the analysis of the data flow program.

【0052】

If a thread is available to process the block according to specific program code (step 910), the thread determines if there is a block in the queue (step 920). If there are blocks, the available threads select the blocks from the queue for processing (step 930). Blocks are typically selected from the queue based on their placement order in the queue. On the other hand, when the thread determines that the selected block depends on the execution of program code for another block that has not yet been executed (step 940), the thread skips the selected block (step 950). On the other hand, when all block dependencies are satisfied (step 940), the thread uses the assigned processor to execute the program code associated with that block (step 960). This process ends when the thread processing the dataflow program dequeues all blocks in the pending queue (step 920).

【0053】

10A-10C illustrate a portion of the queue in FIG. 7 for the purpose of illustrating the execution of a data flow program according to process 900. The portion includes the first five blocks of region 100 queued for processing. As shown in FIG. 10A, each thread uses one of the processors to process the selected block. In this example, there are 4 threads and 4 processors. When the thread completes processing, it executes the next available block in the queue. For example, as shown in FIG. 10B, when one thread completes the program execution of the block of label (1,1), the block of label (1,2) is executed. However, the block with label (1,2) depends on the final states of other blocks, namely blocks (2,1), (3,1) and (4,1), which are still scheduled to be executed. As shown in FIG. 10C, once the execution of the program code for all of these blocks is completed, the thread can continue processing the blocks (1,2). To avoid suspending and not using computational resources efficiently, threads skip processing blocks in the queue and continue processing other blocks in the queue according to the dependencies associated with each block in the queue. It may be a thing. Also, although FIG. 10 shows four threads and four processors, the number of threads or processors may be less or more depending on the particular system configuration.

【0054】

User-optimized specifications The following description includes details of additional specifications that the user can provide to optimize the data flow program. Memory area specifications using tools According to one implementation, the memory area can be specified by the user by using the tool 522 and giving the following control flow variables. Name: Specific name Type: Determining whether the memory area is an input, output, input / output, or temporary space used only while seeking a solution to the problem. Type: Control flow of elements in the memory area The type corresponding to the data type, that is, whether it is an integer or a real number, etc. Dimension: The scalar quantity is 0, the vector is 1, and the matrix is 2. Higher dimensions can also be used. Size: The size of each dimension of the memory area Grid: The size of each dimension of the block in the memory area First dimension: The dimension size of the first matrix (if the memory area is larger than the matrix, keep that size) [0055]

Macro for program code It is also useful to be able to access and operate block elements for control flow program code that executes operations on blocks. Macros are provided that allow users to write program code using control flow formats. In addition, the operation will be executed on the block of each node of the directed acyclic graph. Macros are used in the program code to access specified elements and block attributes in the memory area. Taking a block in a memory area as an argument, the macro can return, for example, the row or column number of the block, or the row or column number of the memory area. Table 3 below lists typical examples of various macros. The user can insert a macro into the program code, and the macro will act on a block of memory area.

【0056】

[Table 3]

<img file="JP2000285084A_D0004.tif" />【0057】

FIG. 11 shows a typical example of a memory area 1100 including a block having elements arranged in 10x10. Assuming that the memory area 1100 with block 1102 is arranged as shown, the following macro finds the numerical value for block 1102 as shown in Table 4.

【0058】

[Table 4]

<img file="JP2000285084A_D0005.tif" />【0059】

Recursive program code can be used, but it should be noted that in this recursive program code, smaller areas are repeatedly allocated. In this case, the recursive process stops when the base case is reached and the area is no longer large enough to repeat the process. Certain program code can be associated with a recursive process, which runs only for its base case. The following recursive macro finds each level shown in Table 5.

【0060】

[Table 5]

<img file="JP2000285084A_D0006.tif" />【0061】

In addition, the program code can be designed as a subdirected acyclic graph, which means that the nodes of the program code are replaced by the subdirected acyclic graph. As a result, a hierarchical structure of a directed acyclic graph can be constructed.

【0062】

Dependence As mentioned above, if the dependencies between blocks are identified and the dependencies specify blocks that need to be executed before other blocks, these dependencies are in a directed acyclic graph that in turn represents the order of execution. Determine the connection between the nodes of. Often, some blocks of memory area depend on some other blocks of the same memory area. To make it easy to specify dependencies between blocksets in a state, Tool 522 provides the user with additional functionality to allow users to quickly specify dependencies between blocks.

【0063】

FIG. 12A shows the parent block 1204 of blockset 1204 (or state) using the user interface in one embodiment of the invention. In this embodiment, the parent block 1202 represents the upper left corner, which is the starting point of the parent block set to be designated. The user then specifies whether the dependency on this parent block 1202 is fixed or free in rows and columns. 12B-12D show various designated combinations given a typical dependent block set 1204. If the user specifies a fixed dependency, all blocks in the dependent block set 1204 will depend on the processing of the parent block 1202 (FIG. 12A). When free with respect to rows, the dependent blocks change (from the upper left block) as the row position of the dependent block set 1204 changes (Figure 12B). Similarly, if the dependencies are free with respect to the columns, the dependent blocks change (from the upper left block) as the position of the columns in the dependent block set 1204 changes (Figure 12C). If the dependencies are free in rows and columns, the dependent blocks change as the position of the dependent blockset changes (Figure 12D). According to this method of specifying dependencies, the tool 522 allows the user to more easily specify multi-block dependencies.

【0064】

Distributed Tool 522 allows the user to allocate "distribution" to a set of blocks in a memory area, and these distributions control how blocks are allocated to the nodes of the directed acyclic graph. These variances are optionally used to group different blocks into a single node, and as a result, different parallel processing schemes can be used to find solutions. For example, assuming that the result of a 3x3 array operation is a 3x3 array, the user would need 9 threads to process on 9 nodes, and each value would be an array operation. Is the result of. However, the user can also require 3 threads to process 3 nodes, in which case each value will result in each column of the array. In the latter case, the node will hold more blocks to process, but less threads. The change in the distributed state allows the user to select a parallel processing scheme as the case may be.

【0065】

To specify the distribution, the user selects a rectangular area of memory area that identifies the blockset. In addition to deciding which block assignments to nodes, distribution also controls which block macros operate. There are two main categories of variance, the first and the second. The difference between the first and second variances is that macros can only operate on blocks on the first variance. They do not operate on the blocks in the second variance. In addition, each memory area can have only one first variance, which determines how many nodes there are in the directed acyclic graph to solve the problem.

【0066】

In the second distribution, if a block in the distribution is added to a node during processing, other blocks in the distribution will also be added to the same node. This makes it easier to identify dependencies.

【0067】

Variance is also in any of the various categories: first single, second "plurality of rows", second "plurality of columns", second "all", and "plurality" (third). Either 1 or 2).

【0068】

The first single variance controls how many directed acyclic graphs are generated. If the first single distribution exists in the memory area, one directed acyclic graph node will be created for each block in that distribution. Each block in the first single distribution will enter its own node, but no two blocks in a given first single distribution will share the same node. If there are more than one variance to solve the problem, i.e. each of two or more memory areas, they have the same size and form. There must be. The reason is that each will have one block that goes into each directed acyclic graph.

【0069】

For all other types of variance, the variance is visually the first single variance to determine which block in the variance is added to the node attached to the first single variance block. Represented above. The block on the first single distributed block is added to the node holding the first single distributed block below it. As will be described later, for the second distribution, other blocks associated with that block are also added to the same node.

【0070】

The three types of exclusive second distributions include blocks that cannot be accessed by macros in the program code that perform operations on the blocks. These variances are the second plurality of rows, the second plurality of columns, and the second all variances. When a block in a second multi-row distribution is added to a node, all blocks in that block's row are also added to that node. The distribution of the second plurality of columns is similar, except when all columns are added instead of rows. In the second total variance, when blocks of that variance are added to a node, each block of that variance is added to that node.

【0071】

Multiple variances can be the first or second, and the blocks of the variance can be accessed by macros if they are the first. If the first single variance is greater than the multiple variances, then the multiple variances will iteratively span each section of the first variance, until it covers all. In each iteration, any block of multiple variances resides on a single block of the first variance, and that block enters the same node holding the single block of the first variance below it. become.

【0072】

The variance can also have a substitution attribute. This indicates that the associated attributes will be replaced before the overlay process is applied. This cannot be applied to the first single variance, nor is it valid for the "all" variance.

【0073】

FIG. 13 shows a typical example of the memory area used in the matrix operation problem. As shown in the figure, consider the problem of matrix operation involving three two-dimensional memory areas A, B, and C. It is assumed that each memory area has rows and columns of a certain size and the memory area is divided into square blocks as shown in FIG . The operation A * B = C can be performed in parallel using a variety of different schemes. First, consider a scheme in which each block of C is described by various threads. The block of C is composed by multiplying the block in the corresponding row of A and the block in the corresponding column of B. According to this example, the dashed lines represent the user-generated variance.

【0074】

In the case of 3x3 shown in FIG. 13, since C has the first single variance, there is a one-to-one correspondence between the blocks in that variance and the nodes of the directed acyclic graph. A node is generated in a directed acyclic graph, each of which is a block of C. The second distribution of the operation row of A and the distribution of the operation column of B is to add an appropriate row of A and column of B to each node. For example, when a block of C (1,1) is added to a node, a block of A (1,1) and B (1,1) is also added. Since the A (1,1) block is the second arithmetic row, all blocks in that column are also added to the same node, and so on.

【0075】

Table 6 shows the generated resulting nodes. According to Table 6, ordered pairs identify the rows and columns of each additional block, and hyphens (-) indicate the range of rows and columns when multiple blocks are added from the distribution. I have specified.

【0076】

[Table 6]

<img file="JP2000285084A_D0007.tif" />【0077】

In the first case, information about the C block at each node can be obtained from the code through the use of macros. However, blocks A and B cannot be accessed by macros because their variance is second.

【0078】

FIG. 14 shows the variance of the first A and B generated to solve the same array operation problem. The same blocks A, B and C are associated with each node, but there is a first block of A and B accessible by macro. According to this implementation, there are 9 nodes as follows.

【0079】

[Table 7]

<img file="JP2000285084A_D0008.tif" />【0080】

The program code executed on each node can be represented by the FORTRAN function MATRIX_MULTIPLY, which takes the location, row number and column number of each of the three matrices A, B and C as arguments.

【0081】

[Table 8]

<img file="JP2000285084A_D0009.tif" />【0082】

Figure 15 shows other possible matrix operation schemes in which each thread processes a sequence of blocks in C. This can be done by the dispersion shown in FIG. In this case, only 3 nodes are generated, because there are 3 blocks in the first single variance. When the variance of the math column spans the first single variance, each block on the first single variance block is as the first variance block along the other blocks of the same column of the math column variance. Added to the same node. According to this example, for the variance of the second arithmetic sequence of B, B (2,1) covers C (1,1) and is added to the node holding C (1,1). .. The reason is that it is the variance of the arithmetic sequence, and block B (2,2), which is in the same column as B (2,1), is also added to the same node. Also, when a block from A is added to a node, all blocks from A are added to that node according to its second total variance.

【0083】

[Table 9]

<img file="JP2000285084A_D0010.tif" />【0084】

The use of this scheme requires that the program code be rewritten as follows:

【0085】

[Table 10]

<img file="JP2000285084A_D0011.tif" />【0086】

FIG. 16 shows another example in which A is calculated as a replacement of B to form C. By using the substitution attribute, the scheme from the previous example can be used with a slight modification.

【0087】

Conclusion Thus, the methods, systems and products according to the invention allow developers to easily develop data flow programs and transform existing control flow programs according to the data flow model. The interface runs in a multiprocessor environment by allowing the developer to define memory areas and divide them into blocks with corresponding states (each associated with a particular instruction in a control flow program). Facilitates the development of data flow programs for The components of the program utilize the control flow programming method, but the program as a whole is designed using the data flow type method. Moreover, each block contains a set of data, which means that the program code associated with each block does not necessarily process a scalar or a single data item. This method is more useful for data-intensive programming systems that require large amounts of data processing, where components can be easily processed in parallel in a multiprocessor computer system. Become a thing.

【0088】

Further, the method according to the present invention can be applied to all programs executed on a multiprocessor system regardless of the computer programming language. For example, Fortran 77 is a commonly used programming language for developing programs that run on multiprocessor computer systems.

【0089】

The above description of embodiments of the present invention is provided for illustration and explanatory purposes. It does not cover all aspects of the invention, nor does it limit the invention to the disclosed detailed embodiments. Modifications and changes can be made in light of the above teachings, and implementation of the present invention may result in modifications and changes. For example, although the above embodiment includes software, the present invention may be implemented as a combination of hardware and software, or may be implemented as hardware alone. The present invention may be implemented using both object-oriented and non-object-oriented programming systems. The scope of the invention is defined by claims and their equivalents.

[Simple explanation of drawings]

[Figure 1]

It is a figure which showed an example of the data flow graph for the calculation of a specific expression.

[Figure 2]

It is a block diagram which showed an example of the memory area defined by the method which concerns on this invention.

[Fig. 3A]

It is a block diagram which showed an example of the dependency between the blocks of the memory area shown in FIG.

[Fig. 3B]

It is a block diagram which showed an example of the dependency between the blocks of the memory area shown in FIG.

[Fig. 4]

It is a figure which showed an example of the directed acyclic graph which showed the dependency relation corresponding to FIG. 3A and FIG. 3B.

[Fig. 5]

It is a block diagram of a typical data processing system in which the present invention is implemented.

[Fig. 6]

It is a flowchart of the operation executed by the data flow program development tool which concerns on this invention.

[Fig. 7]

It is a figure which showed an example of the queue corresponding to the execution order of the data flow program by this invention.

[Fig. 8]

It is a block diagram of a typical multiprocessor computer system suitable for carrying out the method and system which concerns on this invention.

[Fig. 9]

It is a flowchart of the operation performed at the time of execution of the data flow program by this invention.

[Fig. 10A]

It is a block diagram for demonstrating the execution cycle of the data flow program which concerns on this invention.

[Fig. 10B]

It is a block diagram for demonstrating the execution cycle of the data flow program which concerns on this invention.

[Fig. 10C]

It is a block diagram for demonstrating the execution cycle of the data flow program which concerns on this invention.

[Fig. 11]

It is a figure which showed the typical example of the memory area which contains the block which contains the element which concerns on this invention.

[Fig. 12]

It is a figure for demonstrating the generation of the dependency between the block sets which concerns on this invention.

[Fig. 13]

It is a figure which showed the typical example of three memory areas which have the block allocated to the distributed group which concerns on this invention.

[Fig. 14]

It is a figure which showed the typical example of three memory areas which have the block allocated to the distributed group which concerns on this invention.

[Fig. 15]

It is a figure which showed the typical example of three memory areas which have the block allocated to the distributed group which concerns on this invention.

[Fig. 16]

It is a figure which showed the typical example of three memory areas which have the block allocated to the distributed group which concerns on this invention.

[Explanation of symbols]

500 data processing system 510 computer system 520 main memory 530 Secondary storage 540 central processing unit 550 input device 560 Image display device 570 network