CN102760187B - Time factor and space factor synthesized FPGA (Field Programmable Gate Array) task placement method - Google Patents

Abstract

The invention discloses an FPGA task placement method that integrates time factors and space factors. The present invention firstly abstracts the FPGA and the tasks executed on the FPGA into a rectangular block with a certain length and width. Then, two time attributes are recorded for each newly arrived task, that is, the time of arrival in FPGA (referred to as arrival time), and the execution time in FPGA (referred to as execution time). Finally, by comprehensively considering the arrival time of tasks, execution time and space matching between tasks and free blocks, a cost function is designed to select the appropriate placement for tasks. The invention comprehensively considers the overlapping length of tasks and idle blocks in space and time, so that the tasks are compactly placed in the FPGA, thereby reducing the free fragment space in the FPGA and improving the space utilization rate of the FPGA.

Description

FPGA Task Placement Method Combining Time and Space Factors

technical field

The present invention relates to a method for placing FPGA tasks that integrate time and space factors. More specifically, by comprehensively considering the arrival time, execution time, and space matching of tasks and free blocks, a cost function is set to select a suitable placement for tasks. Location.

Background technique

FPGA is composed of reconfigurable resources and has dynamic local reconfigurable characteristics.

FPGA and the tasks executed on FPGA can be abstracted into a matrix with a certain length and width, and each element in the matrix represents a reconfigurable unit.

Each task has two time attributes, that is, the time when it arrives at the FPGA (referred to as the arrival time) and the time when it starts executing in the FPGA (referred to as the execution time).

The process of executing a task in the FPGA includes three steps: first, the CPU selects a reconfigurable resource block with the same space size as the task in the FPGA, that is, task placement; second, the CPU schedules the task to the free block to start execution, that is, Task execution; finally, the FPGA exits after the task execution is completed, and the FPGA reconfigures the reconfigurable units occupied by the task to become idle, that is, the task exits.

FPGA has the characteristic of dynamic local reconfigurability, which can ensure that multiple tasks can occupy different reconfigurable unit blocks in FPGA and execute in parallel without interfering with each other.

An appropriate task placement method can make full use of the free space in the FPGA, so that multiple tasks can be executed in parallel in the FPGA, thereby effectively improving the utilization of the FPGA and shortening the completion time of the task queue.

At present, the commonly used task placement methods on FPGA are first fit and best fit. They both use a linked list to record the free blocks in the FPGA. When there is a task to be executed, find a free block that is not smaller than the size of its matrix as its placement position.

First fit selects the first free block that meets the conditions it finds. This method is more efficient, but it will cause a large amount of fragmented space in the FPGA, resulting in poor FPGA utilization.

Best fit will traverse all free blocks, and use the free matrix that meets the following conditions as the placement position of the task: that is, the perimeter or area of the free matrix is not smaller than the free block, and compared with other free blocks, the free block is similar to the task block The difference in perimeter or area is minimal. Compared with first fit, best fit can effectively improve FPGA utilization.

Contents of the invention

The object of the present invention is, for the problem that proposes in the above background technology, provide a kind of FPGA task placement method that integrates time factor and space factor to select optimal placement position for task, improve the space utilization rate of FPGA.

In order to achieve the above object, the idea of the present invention is: according to (1) the smaller the degree of fragmentation, the more compact the task is placed, the higher the space utilization rate; (2) the higher the overlapping degree of adjacent tasks in the FPGA in space and time , the smaller the fragment, the more compact the task. The present invention comprehensively considers the overlapping lengths of tasks and space blocks in time and space, so that the tasks are compactly placed in the FPGA, thereby reducing fragmented space in the FPGA and improving the space utilization rate of the FPGA.

According to above-mentioned inventive concept, the present invention adopts following technical scheme:

An FPGA task placement method that integrates time factors and space factors is characterized in that the operation steps are as follows: firstly, the FPGA and the tasks executed on the FPGA are abstracted into rectangular blocks with a certain length and width. Two temporal attributes are then recorded for each newly arriving task: the moment of arrival at the FPGA and the time of execution within the FPGA. Finally, by comprehensively considering the task's arrival time, execution time and space matching between the task and the free block, a cost function is designed to select the appropriate placement location for the task.

The expression of cost function described in the present invention is defined as:

in

The meanings of the symbols in the formula are: present_moment is the current moment, Indicates the overlapping length of the adjoining sides of the i-th adjacent task when the newly arrived task is placed in a certain placement position, is the degree of overlap between the newly arrived task and the i-th adjacent task in the time dimension, is the execution time of the i-th adjacent task, is the start time of the i-th adjacent task, is the execution time of the newly arrived task;

There are three cases in the formula: Case 1, the completion time of the newly arrived task is earlier than the completion time of the adjacent task; Case 2, the adjacent edge of the newly arrived task is the FPGA boundary, and the completion time of the adjacent task is recorded as infinite ; Case 3, the completion time of the newly arrived task is later than the completion time of the adjacent tasks.

The two constants in the formula means: is set so that , that is, to ensure that the cost function value of case 1 is greater than the cost function value of case 2. and is set so that , that is to ensure that the cost function value of case 3 is smaller than the cost function values of case 2 and case 1.

Compared with the prior art, the present invention has the following obvious outstanding substantive features and significant progress:

The invention comprehensively considers the overlapping lengths of tasks and idle blocks in space and time, so that the tasks are compactly placed in the FPGA, thereby reducing space fragments in the FPGA and improving the space utilization rate of the FPGA.

Description of drawings

Fig. 1 is the flowchart of the fourth embodiment.

Detailed ways

Preferred embodiments of the present invention are described as follows in conjunction with the accompanying drawings:

Embodiment one:

The FPGA task placement method that integrates time and space factors is as follows: first abstract the FPGA and the tasks executed on the FPGA into a rectangular block with a certain length and width; then record two time attributes for each newly arrived task: The moment of arrival at the FPGA—referred to as the arrival time and the execution time in the FPGA—referred to as the execution time; finally, by comprehensively considering the arrival time of the task, the execution time and the space matching between the task and the free block, the cost function is designed Choose a suitable placement for the task.

Embodiment two:

This embodiment is basically the same as Embodiment 1, and the special features are as follows:

The cost function should take into account the influence of the following factors: (1) in space, the overlapping length of the adjacent task between the newly arrived task and the adjacent task at the placement location; (2) in time, the distance between the newly arrived task and the placement location The degree of overlap between the execution times of adjacent tasks.

The expression of the cost function is defined as:

in

The meanings of the symbols in the formula are: present_moment is the current moment, Indicates the overlapping length of the adjoining sides of the i-th adjacent task when the newly arrived task is placed in a certain placement position, is the degree of overlap between the newly arrived task and the i-th adjacent task in the time dimension, is the execution time of the i-th adjacent task, is the start time of the i-th adjacent task, is the execution time of the newly arrived task;

There are three cases in the formula: Case 1, the completion time of the newly arrived task is earlier than the completion time of the adjacent task; Case 2, the adjacent edge of the newly arrived task is the FPGA boundary, and the completion time of the adjacent task is recorded as infinite ; Case 3, the completion time of the newly arrived task is later than the completion time of the adjacent tasks.

The two constants in the formula means: is set so that , that is, to ensure that the cost function value of case 1 is greater than the cost function value of case 2. and is set so that , that is to ensure that the cost function value of case 3 is smaller than the cost function values of case 2 and case 1.

Embodiment three:

This embodiment is basically the same as Embodiment 2, and the special features are as follows:

In the FPGA task placement method of the integrated time factor and space factor, the cost function seeking method is as follows:

(1). Compare the completion time of the newly arrived task (the current moment present_moment plus the execution time of the new task) with the completion time of the i-th task (the actual start time of the i-th task plus the execution time of the task). If the former is larger, then skip to step (2); if the latter is larger, then skip to step (3); if both are the same, then skip to step (4).

(2). Calculate the overlapping length , overlap for multiplied by a constant , skip to step (5);

(3). Calculate the overlapping length , overlap For the execution time of the newly arrived task, skip to step (5);

(4). Calculate the overlapping length , overlap Multiply the execution time for newly arrived tasks by a constant , skip to step (5);

(5). By the formula Find the value of the cost function.

Embodiment four:

This embodiment is basically the same as the third embodiment, which is an example:

Suppose the current time is 10, and the execution time of the newly arrived task is 4. At this time, there are two existing tasks in the FPGA. The start time of task 1 is 8, and the execution time is 5; the start time of task 2 is 6, and the execution time is 10.

Then set the constant k1=0.5, k2=0.4, then the solution process of the cost function of the new task placement position is as follows:

S1. Comparing the completion time of the newly arrived task and task 1. 10+4>8+5, that is, the completion time of the newly arrived task is greater.

S2. The overlapping length is 5+8-10=3, and the overlapping degree is 3*0.4=1.2.

S3. Comparing the completion time of the newly arrived task and task 2. 10+4<10+6 means that the completion time of task 2 is large.

S4. Overlap length=overlap degree=4.

S5. By the formula It is obtained that the cost function value of the newly arrived task placement position = 3*1.2+4*4=19.6.

Claims (2)

1. a FPGA task laying method for generalized time factor and space factor, is characterized in that operation steps is: first FPGA and the task of performing on FPGA are abstracted into the rectangular block with certain length and width; Then two time attribute are all recorded to each newly arrived task: the moment arriving FPGA, i.e. due in, and the time performed in FPGA, i.e. execution time; Finally, by considering the spatial match of the due in of task, execution time and task and free block, design cost function is the placement location that task choosing is suitable;

Described cost function should consider the impact of following factor: (1) spatially, newly arrives the overlap length of the adjacent task adjacent side of task and placement location; (2) on the time, the new degree of overlapping arriving the adjacent task execution time of task and placement location;

The expression formula of described cost function is defined as:

Wherein

In formula, the connotation of each symbol is respectively: present_moment is current time, when expression is newly placed on certain placement location to task, the adjacent side overlap length of i-th task be adjacent, for new to task task adjacent with i-th degree of overlapping on time dimension, be the execution time of i-th adjacent task, be the start time of i-th adjacent task, for newly arriving the execution time of task;

Be divided into three kinds of situations in formula: situation 1, the moment that completes newly to task completes the moment early than adjacent task; Situation 2, the adjacent edge newly to task is FPGA border, being then designated as adjacent task, to complete the moment be infinite; Situation 3, newly to task complete that the moment is later than adjacent task complete the moment; Two constants in formula meaning be: setting be to make , namely ensure that the cost function value of situation 1 is greater than the cost function value of situation 2; And setting be to make , namely ensure that the cost function value of situation 3 is less than the cost function value of situation 2 and situation 1.

2. the FPGA task laying method of generalized time factor according to claim 1 and space factor, is characterized in that described cost function asks method as follows:

(1). that newly arrives task completes the moment: added by current time present_moment and new to compare, if the former greatly, then jumps to step (2) to the execution time of task and the moment that completes of i-th task; If the latter is large, then jump to step (3); If equally large, then jump to step (4); I-th described task complete the execution time that actual start time that the moment is i-th task adds this task;

(2). obtain overlap length , degree of overlapping for multiplication by constants , skip to step (5);

(3). obtain overlap length , degree of overlapping for newly arriving the execution time of task, skip to step (5);

(4). obtain overlap length , degree of overlapping for the execution time multiplication by constants of newly arriving task is multiplied by , skip to step (5);

(5). by formula try to achieve cost function value.