KR20120004087A - Lockless memory controller for multiprocessor and multiprocessor system using the memory controller - Google Patents

Abstract

PURPOSE: A lock-free memory controller and a multiprocessor system using the lock-free memory controller are provided to process shared data in parallel without a need that each processor uses a locking function, thereby linearly increasing processing performance due to an increase in the number of processors. CONSTITUTION: A memory(610) stores shared data. A processor(620) manages a data block of the memory as one data area. A memory controller(630) provides specific data to the processor by a control signal of the processor. If the control signal is a write command, the memory controller reads data of a write address from the memory, stores the data in a temporary buffer, stores write data in a corresponding bit of the temporary buffer, and stores the data of the temporary buffer in the memory.

Description

LOCK-FREE MEMORY CONTROLLER AND MULTIPROCESSOR SYSTEM USING THE LOCK-FREE MEMORY CONTROLLER}

Embodiments of the present invention relate to a multiprocessor system.

The present invention is derived from a study conducted as part of the IT industry source technology development project of the Ministry of Knowledge Economy and the Ministry of Information and Communication Research and Development (Task Management Number: KI002197, Task name: Scalable microflow processing technology development).

Due to the development of IT technology, the performance and capacity of a single processor have been continuously increased by increasing the clock speed of the processor and the high density transistor technology.

However, due to the increase in the clock speed of the processor and the performance improvement due to the integrated transistor technology, the parallel processing technology that improves the processing performance by performing parallel processing using multiple processors is becoming more common than the improvement of the processing performance by a single processor. It is true.

In the case of processor parallel processing technology, it is necessary to divide data to be processed into parallel processing units so that each processor can process in parallel. Each processor operates in parallel so that each processor simultaneously uses shared resources. Sometimes it happens.

In general, when a processor uses a shared resource at the same time, the shared resource is used by one processor to lock the lock, and then the lock is released and one of the other processors locks the released resource. Then we went back to the flow using resources.

In this case, as a plurality of processors cannot be used at the same time for a shared resource and sequentially used, there is a problem in that the performance of parallel processing is degraded and the performance of one processor is similar.

One embodiment of the present invention is to improve the performance of parallel processing of the shared data without the processor lock function by configuring a memory controller shared by a plurality of processors to a plurality of ports.

In addition, an embodiment of the present invention is a system that can process the data in parallel with the increase in the number of processors to process the data in parallel, without having to use the lock function for each processor shared data The purpose is to provide.

Multiprocessor system according to an embodiment of the present invention, the memory for storing shared data; A processor for managing one or more data blocks of the memory into one data area; And a memory controller configured to provide specific data of the shared data to the processor according to a control signal received from the processor, wherein the processor is exclusive of another processor of bits of the data block when writing data referenced by another processor. Write the data in at least one bit area, and read the data of the entire one or more data blocks when the data is read, wherein the memory controller reads write address data from the memory if the control signal is a write command. Read and store in the temporary buffer, write data to the corresponding bit of the temporary buffer, and then store the temporary buffer in the memory, and read the read address data from the memory to the processor if the control signal is a read command. To provide .

According to an embodiment of the present invention, data can be processed in parallel without using a lock function for each processor to share data, thereby linearly increasing processing performance according to an increase in the number of processors.

1 illustrates a loop code based on a multiprocessor system according to an embodiment of the present invention.
2 is a diagram illustrating code in each processor based on a multiprocessor system according to an embodiment of the present invention.
3 is a diagram illustrating a code execution process in an initial processor based on a multiprocessor system according to an embodiment of the present invention.
4 is a diagram illustrating a data structure when using a lock function based on a general multiprocessor system.
5 is a diagram illustrating an operation of a processor when using a locking function based on a general multiprocessor system.
6 is a block diagram illustrating a configuration of a multiprocessor system according to an embodiment of the present invention.
7 illustrates a data structure provided through a multiprocessor system according to an embodiment of the present invention.
8 is a diagram illustrating a process of executing a code of a processor by a multiprocessor system according to an embodiment of the present invention.
9 illustrates a processor operation by a multiprocessor system according to an embodiment of the present invention.
10 is a diagram illustrating a pattern check data structure of a packet checker according to an embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings and accompanying drawings, but the present invention is not limited to or limited by the embodiments.

On the other hand, in describing the present invention, when it is determined that the detailed description of the related known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted. The terminology used herein is a term used for appropriately expressing an embodiment of the present invention, which may vary depending on the user, the intent of the operator, or the practice of the field to which the present invention belongs. Therefore, the definitions of the terms should be made based on the contents throughout the specification.

1 illustrates a loop code based on a multiprocessor system according to an embodiment of the present invention.

As shown in FIG. 1, a multiprocessor system according to an exemplary embodiment of the present invention is a parallel program that is executed sequentially based on a loop code composed of a for statement or a while statement, and the like.

For example, the loop code sequentially performs the body code (s) while changing the variable i from 0 to 99 as shown in FIG. 1, and in this case, the body code (s) sequentially performs 100 times. When two processors divide the code of FIG. 1 and execute in parallel, it is possible to theoretically increase the processing speed by 2 times, and increase the processing speed linearly in proportion to the number of processors by 4 times when using 4 processors. It is possible to let.

However, if multiple processors execute the loop code in parallel, the variable i is shared, so the data consistency is not good and the body code (s) is not executed 100 times. 200 times.

A case where the code of FIG. 1 is interpreted as a code in each processor will be described in more detail as follows.

2 illustrates code in each processor based on a multiprocessor system according to an embodiment of the present invention, and FIG. 3 illustrates code in an initial processor based on a multiprocessor system according to an embodiment of the present invention. A diagram illustrating the execution process.

For example, each processor reads variable i from shared memory and stops execution if it is greater than or equal to 100, executes code if body code (s) is less than 100, and sets variable i by 1 Modifies and stores the variable i in shared memory.

When two processors execute code in parallel as shown in FIG. 2, since the shared memory is one, even if two processors simultaneously read the variable i, the memory controller reads and supplies the variable i sequentially, FIG. 3. Processor 0 reads 0 as variable i and then processor 2 reads 0 as variable i in the same memory location.

For example, processor 1 shown in FIG. 3 executes the code at t = 2 and then increases variable i to store 1 in memory, and processor 2 executes the code at t = 3 and then increases variable i. Store 1 in memory.

In other words, processor 2 stores 1 in t = 4, but stores 1 in memory, incrementing 1 by 0 to check variable i without storing 2 as desired. As a result, each processor executes the code 100 times each, resulting in a total of 200 times.

4 is a diagram illustrating a data structure when using a lock function based on a general multiprocessor system.

To compensate for the increase in the execution result as described above, the processor adds the lock variable lock to the memory as shown in FIG. 4 and changes the lock variable lock to 1 when the lock variable lock is 0 to perform the lock and read the variable i. It is desirable to store the increased variable i in memory and set the lock variable lock to 0 to give the other processor an opportunity to use the variable i.

In the same way, another processor uses the lock variable lock to loop through variable i, then stores the incremented variable i in memory and sets the lock variable lock to 0, thereby making the variable i available to other processors. Can be provided.

5 is a diagram illustrating an operation of a processor when using a locking function based on a general multiprocessor system.

In this case, as shown in FIG. 5, two processors alternately perform an operation to perform 100 times in total, and then stop the process. However, since the two processors perform sequentially, a similar process is similar to a case in which one processor performs continuously. Performance is provided.

The multi-processor system according to an embodiment of the present invention is to provide a configuration and method that further complements the above-described processor structure and technology operating method.

6 is a block diagram illustrating a configuration of a multiprocessor system according to an embodiment of the present invention, where n may be two or more natural numbers.

As illustrated in FIG. 6, a multiprocessor system according to an embodiment of the present invention may include a memory 610 for storing shared data and a multiprocessor for managing one or more data blocks of the memory 610 as one data area. 620 and a memory controller 630 which provides specific data among the shared data to the multiprocessor 620 according to a control signal received from the multiprocessor 620.

In this case, when one of the multiprocessors 620 according to an embodiment of the present invention writes data referred to by another processor, the data is written to one or more bit areas exclusive of another processor among the bits of the data block, and the data is read. If the data of the entire data block is read.

In addition, when the control signal is a write command, the memory controller 630 reads write address data from the memory 610 and stores the write address data in a temporary buffer, and stores the write data in a corresponding bit of the temporary buffer. After that, the temporary buffer is stored in the memory 610, and when the control signal is a read command, the temporary buffer is read from the memory 610 and provided to the processor that has requested a read.

In this case, the memory controller 630 according to an embodiment of the present invention may manage the data structure as one address, and the memory 610 according to an embodiment of the present invention preferably uses a memory module capable of burst mode. .

The memory controller 630 according to an embodiment of the present invention includes a command queue 631 and an instruction executor 632 in a structure having multiple ports to provide an interface to the multiprocessor 620.

In this case, the instruction queue 631 according to an embodiment of the present invention receives and stores a read and write command from a processor and provides read data for a read command to the processor.

In addition, the instruction executor 632 according to one aspect of the present invention decodes an instruction from the instruction queue 631 and provides corresponding data.

For example, the command executor 632 according to one embodiment of the present invention reads data of a write address from a memory after storing a write command in a temporary buffer and stores write data in a corresponding bit of the temporary buffer. Data is stored in the memory 610.

As another example, the command executor 632 according to an embodiment of the present invention reads data of a read address from the memory 610 and provides it to the command queue 631 in the case of a read command.

In this case, according to one side of the present invention, the write data may be stored in a temporary buffer exclusively for each processor of the multiprocessor 620.

7 illustrates a data structure provided through a multiprocessor system according to an embodiment of the present invention.

The multiprocessor system according to an embodiment of the present invention uses variable i (i1) of processor 1 and variable i (i2) of processor 2 instead of variable i and lock variable lock as shown in FIG. Connect to the structure to allow access to the same address.

For example, the multiprocessor system according to an embodiment of the present invention, when processors 1 and 2 request to read a variable, provides the variables i1 and i2 together to add a value of the variables i1 and i2 to perform a code when less than 100. If the sum exceeds 100, the code stops running.

In addition, the multi-processor system according to an embodiment of the present invention if the processor 1, 2 requests to write a variable, the data requested by the processor 1 writes only the variable i1 and the data requested by the processor 2 writes only the variable i2, the data You can maintain consistency.

8 is a diagram illustrating a process of executing a code of a processor by a multiprocessor system according to an embodiment of the present invention.

For example, as shown in FIG. 8, according to one side of the present invention, at t = 5, the variable i2 in processor 1 may be 0 or 1, which is a service policy of the memory controller 630 and a command processing of the processor. It may vary depending on the speed.

Such a difference may be remarkable as the number of processors increases, and may occur frequently when the number of executions exceeds 100.

For example, as a result of checking in the processor 1, when the 99th execution is performed, since the processor 2 may be performed in parallel with the processor 1 trying to perform 100 times, the total number of executions may be 101 times.

In order to compensate for the above, the multiprocessor system according to an embodiment of the present invention performs one processor up to 100 times and sets the threshold value of the processor 2 so that the sum of the variable i1 and the variable i2 is less than the threshold value. In this case, it can be designed to execute 100 times in total if the processor 1 executes 100 times and stops executing the code after performing the process by checking the threshold without performing it in parallel when it is larger than the threshold.

9 illustrates a processor operation by a multiprocessor system according to an embodiment of the present invention.

Referring to FIG. 9, as a result of configuring the multiprocessor system according to an embodiment of the present invention with the above configuration, it can be seen that the execution time is reduced by half compared to the processor operation shown in FIG. 5.

According to an embodiment of the present invention, a packet inspector for inspecting and processing a packet of a network may be provided, and since the payload of a packet does not have a predetermined rule and a pattern check takes a lot of time, a pattern using a plurality of processors is generally used. You can check for matches.

Hereinafter, a case in which 100 patterns are matched and whether the number of matches is checked with respect to the payload of a packet input to the packet inspector according to an embodiment of the present invention will be described by way of example.

For example, the packet inspector according to an embodiment of the present invention takes a long time when one processor checks 100 patterns of a payload of a packet, so that the payload of the packet is copied using two processors. Thus, if each processor examines 50 patterns in half, the inspection time can be cut in half.

10 is a diagram illustrating a pattern check data structure of a packet checker according to an embodiment of the present invention.

For example, according to the packet inspection method according to an embodiment of the present invention, as shown in FIG. 9, the variable i1 is the number of times that the processor 1 performs the pattern matching check and the variable mc1 is the number of pattern matching.

That is, according to an embodiment of the present invention, if the variable i1 is 1, the first pattern matching is checked. If the variable i1 is 50, 50 pattern checks are completed. The variable mc1 accumulates and adds the number of pattern matching. If the variable mc1 is 0 when i1 is 50, data means that no pattern is matched. If the variable mc1 is 5, it means that five patterns match the payload of the packet.

Similarly, according to an embodiment of the present invention, the variable i2 is the number of times that the processor 2 performs the pattern matching check, the variable mc2 is the number of the pattern matching, and initially, the variables i1, i2, mc1, and mc2 are all 0s. Is initialized to

Therefore, according to an exemplary embodiment of the present invention, the processor 1 reads the variables i1, i2, mc1, and mc2 to complete the check if the variables i1 and i2 are 50, respectively, and checks the variables i1 and mc1 after the pattern check if the variable i1 is less than 50. Update (variable mc1 updates if necessary).

At this time, in one embodiment of the present invention, the pattern is checked until the variable i1 becomes 50, and when the variable i1 becomes 50, the variable i2 is checked. When the variable i2 is less than 50, the variable i2 is checked while the variable i2 is 50. It stops running.

In this case, according to an embodiment of the present invention, when the variables i1 and i2 are all 50, the sum of the variables mc1 and mc2 may be known to determine the cumulative number of pattern matching.

The configuration of a multiprocessor system according to an embodiment of the present invention is as follows.

Processor 1... Of the multiprocessor system according to an embodiment of the present invention. … n 620 is a processor that is performed in parallel, and instruction queue 631 stores instructions for reading or writing common data structures from each processor of multiprocessor 620 to provide to instruction executor 632. The read data at 632 is delivered to the processor that has requested the read.

In addition, the instruction executor 632 of the multiprocessor system according to an embodiment of the present invention sequentially checks the instruction queue 631 and reads data from a corresponding address of the memory 610 if there is a valid instruction and reads the instruction. If a write command is provided, the data is read from the corresponding address of the memory 610 and stored in the temporary buffer, the bit data corresponding to the processor in the temporary buffer is replaced with the write data, and the data of the changed temporary buffer is written into the memory. do.

In this case, the memory 610 according to an embodiment of the present invention may be used in a variety of memory means such as SRAM, SDRAM, DDR SDRAM, MEMORY MODULE, and the like to store data or provide read data from the command executor 632. do.

According to one aspect of the present invention, it is possible to manage each variable of the data structure with a different address, but it is preferable to manage with one address since it is shared data.

That is, according to one side of the present invention, when each variable size is small, it is preferable to use some bits of data as variables using SRAM and SDRAM, and to use burst memory capable of burst mode when each variable size is large. Do.

For example, if the size of each variable is small, 32-bit data is used as four 8-bit variables. If the size of each variable is large, the data is 64 bits and 64 bytes of data for burst memory MEMORY MODULE. It is possible to use up to 16 32-bit variables by accessing the structure as a single address.

Embodiments according to the present invention can be implemented in the form of program instructions that can be executed by various computer means can be recorded on a computer readable medium. The computer readable medium may include program instructions, data files, data structures, etc. alone or in combination. Program instructions recorded on the media may be those specially designed and constructed for the purposes of the present invention, or they may be of the kind well-known and available to those having skill in the computer software arts. Examples of the computer-readable recording medium include magnetic media such as a hard disk, a floppy disk, and a magnetic tape; optical media such as CD-ROM and DVD; magnetic recording media such as a floppy disk; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of program instructions include not only machine code generated by a compiler, but also high-level language code that can be executed by a computer using an interpreter or the like. The hardware device described above may be configured to operate as one or more software modules to perform the operations of the present invention, and vice versa.

As described above, the present invention has been described by specific embodiments such as specific components and the like. For those skilled in the art to which the present invention pertains, various modifications and variations are possible. Therefore, the spirit of the present invention should not be limited to the described embodiments, and all of the equivalents or equivalents of the claims as well as the claims to be described later will belong to the scope of the present invention. .

610: memory
620: multiprocessor
630: memory controller

Claims (1)

A memory for storing shared data;
A processor for managing one or more data blocks of the memory into one data area; And
A memory controller providing specific data among the shared data to the processor according to a control signal received from the processor
Including,
The processor comprising:
When writing data referenced by another processor, writing the data to one or more bit regions exclusive of another processor of the one or more blocks of data,
When the data is read, characterized in that the data of the entire one or more data blocks are read,
The memory controller,
If the control signal is a write command, read the data of the write address from the memory and store the data in the temporary buffer, write data in the corresponding bit of the temporary buffer, and then store the data of the temporary buffer in the memory,
And when the control signal is a read command, read data of a read address from the memory and provide the processor to the processor.

Images