CN103530130B - The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system - Google Patents
The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system Download PDFInfo
- Publication number
- CN103530130B CN103530130B CN201310514533.7A CN201310514533A CN103530130B CN 103530130 B CN103530130 B CN 103530130B CN 201310514533 A CN201310514533 A CN 201310514533A CN 103530130 B CN103530130 B CN 103530130B
- Authority
- CN
- China
- Prior art keywords
- list item
- queue
- team
- group
- joining
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 22
- 238000003860 storage Methods 0.000 claims abstract description 10
- 238000004519 manufacturing process Methods 0.000 claims abstract description 8
- 238000005304 joining Methods 0.000 claims description 17
- 238000009826 distribution Methods 0.000 claims description 3
- 230000009286 beneficial effect Effects 0.000 abstract description 2
- 238000005516 engineering process Methods 0.000 description 9
- 230000007717 exclusion Effects 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 238000010923 batch production Methods 0.000 description 2
- 230000007423 decrease Effects 0.000 description 2
- 238000000151 deposition Methods 0.000 description 2
- 238000004891 communication Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000009466 transformation Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses the method and apparatus realizing multiple-input, multiple-output queue in a kind of multiple nucleus system, belong to computer application software technical field, a kind of method realizing multiple-input, multiple-output queue, comprise the following steps: the memory space of queue is grouped by S1., N number of list item is divided into one group, in N number of list item, first list item stores effective list item number in this group list item, virtual value is 0 to (N 1), the data of remaining (N 1) individual list item storage Producer, wherein N is the integer more than or equal to 1.Beneficial effects of the present invention is as follows: improve the efficiency of production of units and customers' problems.Reduce this performance bottleneck of the spin lock impact on queue operation under multi-core environment to greatest extent, improve the queue performance under multi-core environment, and then improve the performance of whole multiple nucleus system.
Description
Technical field
The present invention relates to computer application software technical field, particularly relate to one and realize multiple-input, multiple-output queue
Method and apparatus.
Background technology
In systems soft ware, generally use queue as the medium of disparate modules data sharing.Therefore, team
Row are typically used by multiple software patterns, and different software modules is required for when using queue carrying out mutually
Scold, to ensure the integrity of queue.Along with the development of multi-core technology, the intercore communication in multiple nucleus system is usual
It is also adopted by queue technology, because queue technology is fairly simple efficiently, but is as multiple nucleus system center number
Increasing, the visitor of queue is consequently increased, and is required for the access queue of mutual exclusion between core and core, but many
In core system, the mutual exclusion means of similar spin lock etc can be along with the increase of competition, and it is very fast that efficiency can decline,
The efficiency ultimately resulting in queue becomes the lowest.
Traditional queue technology, as it is shown in figure 1, a queue head pointer and rear of queue pointer can be used, head refers to
Pin is used for enqueue operations, and tail pointer is used for dequeue operation, when enqueue operations, it is judged that head pointer add 1 after whether
Equal with tail pointer, if equal, show that queue is the fullest, it is impossible to join the team, if unequal, show queue
Less than, can join the team, after joining the team, head pointer adds 1.Dequeue operation judges that tail pointer and head pointer are the most equal,
If equal, show that queue is empty, it is impossible to go out team, if unequal, show that queue has list item, can go out
Team, after going out team, adds 1 by tail pointer.When queue uses under multi-core environment, grasp owing to there is multiple core simultaneously
Make queue, need to add lock when enqueue operations and dequeue operation and carry out mutual exclusion.
The realization of tradition queue technology there is problems in that in order in how internuclear mutual exclusion, all operations is all lock
Get up.
In multiple nucleus system, the spin lock consumption brought due to competition can make spin lock efficiency seriously reduce, special
It is not as the universal of many-core (being often referred to containing more than 8 CPU), after the number of core increases, this efficiency
Exponentially level declines.Queue technology is the internuclear primary selection communicated, but traditional queue technology by
In needs spin lock as salvo, when using under multi-core environment, performance is the highest, in the urgent need to setting
Count a kind of new queue, under multi-core environment, keep high-performance.The performance of queue to be improved, emphasis improves
It is the performance of spin lock, and improves the performance of spin lock, it is preferred that emphasis is reduce the collision probability of spin lock, with
And the scope of spin lock protection.
In classical producer consumer environment, as in figure 2 it is shown, Producer adds list item in queue, disappear
Expense person takes out list item from queue.Producer completes an operation and is divided into two parts, and one has been to generate stream
Journey (pt1), another has been the flow process (pt2) adding queue.Multiple Producers need during pt2
Wanting the access queue of mutual exclusion, this operation can occur to compete the situation of queue.Consumer in like manner, is also classified into two
Individual flow process, one is to take list item (ct1) from queue, and another is to use this list item (ct2).Multiple disappear
Fei Zhehui is the access queue of mutual exclusion in the time period of ct1.
For needing by the queue of multiple module accesses, it is shared access, it is meant that competition is to certainly exist
, and current computer architecture, the how internuclear increase performance along with competitor can drastically decline, in a large number
Time can consume obtain spin lock, this problem be computer body system structure determine, it is impossible to change.
Therefore, in order to improve the performance of queue under multi-core environment, need a kind of new queue, reduce competition and bring
Overhead.
Summary of the invention
The multinuclear that it is an object of the invention to improve the low present situation of computing power under multi-core environment and propose
The implementation method of multiple-input, multiple-output queue and equipment in system.
In order to realize above goal of the invention, the technical scheme that the present invention takes is as follows: real in a kind of multiple nucleus system
The method of existing multiple-input, multiple-output queue, comprises the following steps:
S1. being grouped by the memory space of queue, N number of list item is divided into one group, in N number of list item, and first table
Storing effective list item number in this group list item, virtual value is 0 to (N-1), and remaining (N-1) individual list item is deposited
The data of storage Producer, wherein N is the integer more than or equal to 1；
S2. the ultimate unit of producers and consumers's operation queue is one group of N number of list item, when Producer has M table
Item to add fashionable, and queue is also one group of N number of list item of distribution, and wherein M is less than or equal to (N-1)；When joining the team, once
Property M list item is inserted queue, the most again M is filled in first list item, represent list item inserted；
When S3. going out group, from queue, disposably go out one group of N number of list item of team, first-selected check from first list item
Effective list item number, after completing effective list item and going out team, resets first list item in queue, table
Illustrate that team completes.
Further, queue full is judged by below equation when joining the team: head pointer+N=tail pointer；If
Equal, show that queue is the fullest, it is impossible to join the team, if unequal, show queue less than, can join the team, enter
After team, head pointer adds N.
Further, queue empty is judged by below equation when going out group: tail pointer=head pointer；If it is equal,
Show that queue is empty, it is impossible to go out team, if unequal, show that queue has list item, team can be gone out, after going out team,
Tail pointer is added N.
Further, also need to the list item number by often organizing in list item when going out team and join the team judge to go out team
Or join the team.
Further, when joining the team, need to judge whether list item number of next group list item is 0, be 0 can to enter
Team.
Further, when going out group, needing the list item number judging next group list item is not the most 0, is not 0 i.e.
Team can be gone out.
Further, in described S2, producers and consumers the most disposably carries out (N-1) secondary production and disappears
Take operation, data of then joining the team in batches and batch data dequeued.
In order to solve the problems referred to above, the invention allows for a kind of multiple nucleus system realizes multiple-input, multiple-output queue
Equipment, the memory space of queue at least includes a packet, and wherein, N number of list item is one group, in N number of list item
First list item be used for storing effective list item number in this group list item, virtual value is 0 to (N-1), its
Remaining (N-1) individual list item is for storing the data of Producer, and wherein N is the integer more than or equal to 1.
Further, queue storage space includes four packets, and often group has four list items.
Further, in four described list items, first list item is used for storing effective table in this group list item
Item number 3, remaining 3 list item is for storing the data of Producer.
Beneficial effects of the present invention: first queue is carried out packet transformation by the present invention, simultaneously by first list item
For storing the packet effective quantity needs with support batch operation, then revise joining the team and going out of tradition queue
Team operates, and the protection of spin lock is only limited to the movement of head and tail pointer, it is achieved that spin lock is protected
Scope and the list item of operation completely irrelevant；The flow process of last producer consumer is in the team supporting batch operation
Under row environment, it is possible to achieve batch production and batch consumption, reach to extend the production and consumption time, reduce same
The probability of Shi Jingzheng queue, improves the performance of queue, finally improves production of units and customers' problems
Efficiency, reduces this performance bottleneck of the spin lock impact on queue operation under multi-core environment to greatest extent,
Improve the queue performance under multi-core environment, and then improve the performance of whole multiple nucleus system.
Accompanying drawing explanation
Fig. 1 is tradition queue storage space structural representation；
Fig. 2 is that in Producer consumer environments, tradition queue goes out team and joins the team schematic diagram；
Fig. 3 is the queue storage space structural representation of the present invention；
Fig. 4 is that the queue of the specific embodiment of the invention 1 goes out team and joins the team schematic diagram；
Fig. 5 is that the queue of the specific embodiment of the invention 2 goes out team and joins the team schematic diagram.
Detailed description of the invention
For making the purpose of the present invention, technical scheme and advantage clearer, develop simultaneously reality referring to the drawings
Execute example, the present invention is described in further details.
A kind of method realizing multiple-input, multiple-output queue in multiple nucleus system, comprises the following steps:
S1. being grouped by the memory space of queue, N number of list item is divided into one group, in N number of list item, and first table
Storing effective list item number in this group list item, virtual value is 0 to (N-1), and remaining list item is used for storing
The data of Producer, wherein N is the integer more than or equal to 1.
S2. the ultimate unit of producers and consumers's operation queue is one group of N number of list item, and wherein (N-1) is used for protecting
Deposit the data of Producer.Even if Producer only has M (M is less than or equal to (N-1)) individual list item to add, queue
Also it is one group of N number of list item of distribution.Therefore, at most can be carried out continuously (N-1) in the production phase secondary for Producer
Producing operation, produce multiple list item, the time is M*pt1.When joining the team, disposably M list item is inserted queue,
Finally M is filled in first list item (first list item represents effective list item number) again, represents with this
List item has been inserted.
S3. going out group person and disposably go out one group of N number of list item of team from queue, first-selection has been checked from first list item
The list item number of effect, after completing effective list item and going out team, resets first list item in queue, represents
Go out team to complete.
Using spin lock to protect whole operating process relative to tradition queue, in the present invention, spin lock is only protected
Head (head) pointer and the moving process of tail (tail) pointer, write and reading for list item are not carried out
Protection, and head and tail pointer is not to operate a list item to move once, but the most mobile N number of position,
For once operate, therefore operator to hold the list item number of time of spin lock and operation unrelated, spin lock
The scope of protection is greatly reduced.
When have multiple join the team and go out group person operate simultaneously time, due to the movement of pointer be protection, each operation
The exercisable region that person obtains is diverse, therefore, and the person of joining the team and go out group person and can operate team simultaneously
Row and unaffected.
When tradition queue judges queue empty and queue full, head+1==tail is used to judge queue full, and
In the present invention, join by component during due to queue, it is therefore desirable to use head+N==tail to judge queue full.
Tradition queue uses tail==head to judge queue empty, in the present invention, stands good.
Owing to the movement of pointer is prior to the write of list item and reading, that is, head and tail pointer has moved
Move, but table entry operation does not complete, therefore, only judge quene state by head and tail pointer
It is unsafe.Such as: in enqueue operations, judge, by head and tail pointer, the space that queue is available free
Can add new list item, it is possible that be currently that dequeue operation moves tail pointer, but list item is
During being in reading, being also not fully complete, at this time enqueue operations is possible to directly cover and is gone out
The list item that team reads.Therefore, go out team and be required for by the list item number often organized in list item to the volume of carrying out with joining the team
Outer judgement, when joining the team, needs to judge that whether the list item number of next group list item is 0 (because list item number is clear
Zero is last operation team).When going out group, need to judge the list item number of next group list item the most not
It is 0 (because assignment list item number is last operation joined the team).
False code:
Dequeue operation:
Producers and consumers at most can disposably carry out (N-1) secondary production and consumption operation, and then batch adds
Enter data and batch data dequeued.Owing to the time of batch production and batch consumption disappears than single production and single
Time-consuming longer, therefore reduce the probability of multiple producers and consumers access queue simultaneously, reduce certainly
The probability of rotation lock conflict, thus improve the performance of queue.Queue simultaneously join the team and dequeue operation just for
Head and tail pointer carries out spin lock protection, is not affected by batch operation, relative to tradition queue
The scope of protection is the least, is greatly reduced the protection domain of queue lock, it also reduces simultaneously and lock
The probability of competition.
The invention allows for realizing in a kind of multiple nucleus system the equipment of multiple-input, multiple-output queue, the storage of queue is empty
Between at least include a packet, wherein, N number of list item is one group, and first list item in N number of list item is used for depositing
Storing up effective list item number in this group list item, virtual value is 0 to (N-1), and remaining (N-1) individual list item is used for depositing
The data of storage Producer, wherein N is the integer more than or equal to 1.
Queue storage space includes four packets, and often group has four list items.In four described list items first
List item is used for storing effective list item number 3 in this group list item, and remaining 3 list item is for storing Producer
Data.
Specific embodiment one: as it is shown on figure 3, queue one has four groups, often group is constituted (N=4) by 4 list items,
Wherein first list item preserves effective list item number, and remaining list item is used for preserving user data, therefore, produces
Person the most at most can insert 3 list items.
Producer adds one group of list item, and as shown in Figure 4, the list item that Producer is to be added is two (M=2).
Queue disposably distributes one group of four list item, and wherein first is used for preserving list item number.Therefore, Producer
When inserting queue, first list item has inserted list item number 2, and remaining 3 list item only takes up two, fills out respectively
A, b are entered.Consumer goes out team from queue, goes out one group of list item of team every time.When going out group list item, need first from
The content of first list item judges there is several effective list item in this group, in this example embodiment, and effective list item one
It is 2 altogether, the most once goes out 2 list items of team and process.
Specific embodiment two: as it is shown on figure 3, queue one has four groups, often group is constituted (N=4) by 4 list items,
Wherein first list item preserves effective list item number, and remaining list item is used for preserving user data, therefore, produces
Person the most at most can insert 3 list items.
Producer adds one group of list item, as it is shown in figure 5, Producer list item to be added is three (M=3).
Queue disposably distributes one group of four list item, and wherein first is used for preserving list item number.Therefore, Producer
When inserting queue, first list item has inserted list item number 3, and remaining 3 list item has been respectively filled in a, b, c.
Consumer goes out team from queue, goes out one group of list item of team every time.When going out group list item, need first from first list item
Content judge that this group has several effective list item, in this example embodiment, effective list item comes to 3, so
After once go out 3 list items of team and process.
Those of ordinary skill in the art is it will be appreciated that embodiment described here is to aid in reader's reason
Solve the implementation of the present invention, it should be understood that protection scope of the present invention is not limited to such the oldest
State and embodiment.Those of ordinary skill in the art can make according to these technology disclosed by the invention enlightenment
Various other various concrete deformation and combinations without departing from essence of the present invention, these deformation and combination are still at this
In the protection domain of invention.
Claims (8)
1. the method that a multiple nucleus system realizes multiple-input, multiple-output queue, it is characterised in that comprise the following steps:
S1. being grouped by the memory space of queue, N number of list item is divided into one group, in N number of list item, and first table
Storing effective list item number in this group list item, virtual value is 0 to (N-1), and remaining (N-1) individual list item is deposited
The data of storage Producer, wherein N is the integer more than or equal to 1；
S2. the ultimate unit of producers and consumers's operation queue is one group of N number of list item, when Producer has M table
Item to add fashionable, and queue is also one group of N number of list item of distribution, and wherein M is less than or equal to (N-1)；When joining the team, once
Property M list item is inserted queue, the most again M is filled in first list item, represent list item inserted；
When S3. going out group, from queue, disposably go out one group of N number of list item of team, first-selected check from first list item
Effective list item number, after completing effective list item and going out team, resets first list item in queue, table
Illustrate that team completes.
Method the most according to claim 1, it is characterised in that judge queue by below equation when joining the team
Full: head pointer+N=tail pointer；If equal, show that queue is the fullest, it is impossible to join the team, if unequal,
Show queue less than, can join the team, after joining the team, head pointer adds N.
Method the most according to claim 1 and 2, it is characterised in that sentenced by below equation when going out group
Disconnected queue empty: tail pointer=head pointer；If equal, show that queue is empty, it is impossible to go out team, if not phase
Deng, show that queue has list item, team can be gone out, after going out team, tail pointer is added N.
Method the most according to claim 3, it is characterised in that also need to pass through when going out team and join the team
Often can the list item number in group list item judge team or join the team.
Method the most according to claim 4, it is characterised in that: when joining the team, need to judge next group table
List item number whether be 0, be 0 can to join the team.
Method the most according to claim 5, it is characterised in that: when going out group, need to judge next group table
List item number be not the most 0, be not 0 can to go out team.
Method the most according to claim 1, it is characterised in that: in described S2, Producer and consumption
Person the most disposably carries out (N-1) secondary production and consumption operation, and then batch is joined the team data and gone out team's number in batches
According to.
8. a multiple nucleus system realizes the equipment of multiple-input, multiple-output queue, it is characterised in that: including: packet mould
Block, module of joining the team and go out group module；
Described grouping module, for being grouped by the memory space of queue, N number of list item is divided into one group, N number of
In list item, first list item stores effective list item number in this group list item, and virtual value is 0 to (N-1),
The data of remaining (N-1) individual list item storage Producer, wherein N is the integer more than or equal to 1；
Described module of joining the team, for when Producer, to have M list item to add fashionable, wherein M is less than or equal to (N-1)；
When joining the team, disposably M list item is inserted queue, the most again M is filled in first list item, represent table
Item has been inserted；
Described go out group module, when being used for group, from queue, disposably go out one group of N number of list item of team, first-selected from the
One list item is checked effective list item number, after completing effective list item and going out team, by first in queue
Individual list item resets, there is shown team completes.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310514533.7A CN103530130B (en) | 2013-10-28 | 2013-10-28 | The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310514533.7A CN103530130B (en) | 2013-10-28 | 2013-10-28 | The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103530130A CN103530130A (en) | 2014-01-22 |
| CN103530130B true CN103530130B (en) | 2016-12-07 |
Family
ID=49932170
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310514533.7A Active CN103530130B (en) | 2013-10-28 | 2013-10-28 | The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103530130B (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105162724B (en) | 2015-07-30 | 2018-06-26 | 华为技术有限公司 | A kind of data are joined the team and go out group method and queue management unit |
| CN106371937A (en) * | 2016-08-31 | 2017-02-01 | 迈普通信技术股份有限公司 | Inter-core communication method and device for multi-core system |
| CN110321215A (en) * | 2018-03-29 | 2019-10-11 | 华为技术有限公司 | Queue control method and device |
| CN109656515A (en) * | 2018-11-16 | 2019-04-19 | 深圳证券交易所 | Operating method, device and the storage medium of queue message |
| CN109753479B (en) * | 2018-12-28 | 2021-05-25 | 杭州迪普科技股份有限公司 | Data issuing method, device, equipment and medium |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5974483A (en) * | 1997-05-21 | 1999-10-26 | Microsoft Corporation | Multiple transparent access to in put peripherals |
| CN101800867B (en) * | 2010-01-19 | 2011-09-28 | 深圳市同洲电子股份有限公司 | Method, device and digital-television receiving terminal for realizing ring buffer |
| CN102591815B (en) * | 2011-12-27 | 2015-07-29 | Tcl集团股份有限公司 | A kind of method of loop data buffer read-write batch data and device |
-
2013
- 2013-10-28 CN CN201310514533.7A patent/CN103530130B/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| CN103530130A (en) | 2014-01-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103530130B (en) | The method and apparatus realizing multiple-input, multiple-output queue in multiple nucleus system | |
| Ajima et al. | The tofu interconnect d | |
| CN104168217B (en) | A kind of First Input First Output dispatching method and device | |
| CN102938000B (en) | Method for searching route is shown in flowing without lock of a kind of high-speed parallel | |
| CN106164881B (en) | Work stealing in heterogeneous computing systems | |
| CN102752198B (en) | Multi-core message forwarding method, multi-core processor and network equipment | |
| CN100412848C (en) | Computer architecture and software cells for broadband networks | |
| US8381230B2 (en) | Message passing with queues and channels | |
| CN104461707B (en) | a kind of lock request processing method and device | |
| CN105005546A (en) | Asynchronous AXI bus structure with built-in cross point queue | |
| CN101923491A (en) | Method for thread group address space scheduling and thread switching in multi-core environment | |
| CN105956659A (en) | Data processing device, data processing system and server | |
| CN101040268B (en) | External data interface in a computer architecture for broadband networks | |
| CN106372008B (en) | A kind of data cache method and device | |
| CN108415778A (en) | Task ranking method, device and scheduling system | |
| Erdoğan et al. | Scheduling twin robots on a line | |
| CN109117189A (en) | Data processing method, device and computer equipment | |
| Jeng et al. | A review of synthesis techniques for Petri nets | |
| CN106371937A (en) | Inter-core communication method and device for multi-core system | |
| CN112540936A (en) | Discrete memory access read-write method oriented to heterogeneous many-core architecture | |
| CN106156049A (en) | A kind of method and system of digital independent | |
| CN106375249A (en) | Switching chip data structure, control method and control system thereof | |
| CN118573637B (en) | Stream table unloading method for multi-source access, computer equipment and medium | |
| CN110349076A (en) | The processing method and processing device of data | |
| CN100432968C (en) | Direct access device of storage and data transmission method thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CP02 | Change in the address of a patent holder | ||
| CP02 | Change in the address of a patent holder |
Address after: 610041 15-24 floor, 1 1 Tianfu street, Chengdu high tech Zone, Sichuan Patentee after: MAIPU COMMUNICATION TECHNOLOGY Co.,Ltd. Address before: 610041 Sichuan city of Chengdu province high tech Zone nine Hing Road No. 16 building, Maipu Patentee before: MAIPU COMMUNICATION TECHNOLOGY Co.,Ltd. |
|
| CP02 | Change in the address of a patent holder | ||
| CP02 | Change in the address of a patent holder |
Address after: 610041 nine Xing Xing Road 16, hi tech Zone, Sichuan, Chengdu Patentee after: MAIPU COMMUNICATION TECHNOLOGY Co.,Ltd. Address before: 610041 15-24 floor, 1 1 Tianfu street, Chengdu high tech Zone, Sichuan Patentee before: MAIPU COMMUNICATION TECHNOLOGY Co.,Ltd. |