[go: up one dir, main page]

CN119046205A - Dynamic lottery bus arbitration method and arbitrator based on history adaptation - Google Patents

Dynamic lottery bus arbitration method and arbitrator based on history adaptation Download PDF

Info

Publication number
CN119046205A
CN119046205A CN202411194173.1A CN202411194173A CN119046205A CN 119046205 A CN119046205 A CN 119046205A CN 202411194173 A CN202411194173 A CN 202411194173A CN 119046205 A CN119046205 A CN 119046205A
Authority
CN
China
Prior art keywords
host
lottery
authorized
shift register
interval
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.)
Pending
Application number
CN202411194173.1A
Other languages
Chinese (zh)
Inventor
詹贵阳
冯华
刘功哲
熊民权
马华
李焱明
谭俊江
刘昱玮
黄智勇
陈洁
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shanghai Thinktech Information Technology Co ltd
Original Assignee
Shanghai Thinktech Information Technology Co ltd
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Shanghai Thinktech Information Technology Co ltd filed Critical Shanghai Thinktech Information Technology Co ltd
Priority to CN202411194173.1A priority Critical patent/CN119046205A/en
Publication of CN119046205A publication Critical patent/CN119046205A/en
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/16—Handling requests for interconnection or transfer for access to memory bus
    • G06F13/1605—Handling requests for interconnection or transfer for access to memory bus based on arbitration
    • G06F13/1652—Handling requests for interconnection or transfer for access to memory bus based on arbitration in a multiprocessor architecture
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/58—Random or pseudo-random number generators
    • G06F7/582—Pseudo-random number generators
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

The application relates to a dynamic lottery bus arbitration method and an arbiter based on history self-adaption. Compared with the traditional fixed arbitration and polling arbitration, the method has the main improvements that the number of times that each host is authorized in a period of time is counted, the more the number of times that each host is authorized, the more the number of dynamic lottery tickets is, the more frequently used hosts are indicated, the host is authorized for the next time, the number of times that each host is authorized is recorded through a shift register, the situation that each host is authorized for a period of time is reflected, the host which the system wants to use for the next time can be predicted from the aspect of probability, therefore, the arbiter has self-adaptability and certain predictability, the characteristics of both the fixed arbiter and the polling arbiter are considered, the probability that the host which is used for a long time for many times obtains authorization is high (the characteristic of the fixed arbiter is favored), and the probability that the host which is not frequently used obtains authorization (the characteristic of the polling arbiter is favored) is not completely excluded.

Description

Dynamic lottery bus arbitration method and arbiter based on history self-adaption
Technical Field
The application relates to the technical field of bus arbitration, in particular to a history self-adaption-based dynamic lottery bus arbitration method and an arbiter.
Background
In existing hierarchical storage, an AHB bus is often used to access memory. AHB is a bus protocol, which is the most important part of an advanced microcontroller bus architecture, is an on-Chip bus oriented to high performance, high bandwidth and low delay, and meets the requirements of high-performance and complex SoC (System-on-Chip) design.
AHB buses typically employ a multi-master multi-slave topology. I.e. the same master can send data to different slaves in a time sharing manner, or the same slave can receive data from different masters in a time sharing manner. However, as shown in fig. 1, when multiple hosts apply for sending data to the same slave, the problem of arbitration of authorization of the hosts is involved, and if the permissions cannot be reasonably allocated to multiple hosts with the same or different priorities, the problem of blocking a host in a certain path and reducing the transmission efficiency of the system is easily caused. Therefore, the reasonable allocation of the request authorities of all the hosts is ensured, and the method is an important component for breaking through the performance bottleneck of the SoC.
The basic principle of the arbitration mechanism is that according to the request signals of all the hosts, a gating signal is generated according to a certain arbitration principle, so that the corresponding host can perform data interaction with the slave in a time sharing manner. Arbitration algorithms typically have a fixed priority arbiter and a round robin priority arbiter.
(1) A fixed priority arbiter in which the priority of each processor to access the shared resource is fixed, the priority of the master with the heavier transmission task is relatively high, and if several masters apply for bus usage at the same time, the highest priority device will be granted. The arbitration algorithm has the advantages of simple design and small area consumption. However, since the highest priority master device will always be authorized after the application, other lower priority devices will not be authorized. If a high priority master frequently requests, a low priority master waits too long to get authorization causing starvation.
(2) In the poll arbiter, the priorities of the masters are not fixed, but are rotated in order. The algorithm, in combination with time division multiplexing, can evolve into a time slice based round robin arbitration algorithm. If there are A, B, C hosts, at the beginning, a corresponds to a 0 priority, B corresponds to a1 priority, and C corresponds to a2 priority. Table 0 has the highest priority and table 2 has the lowest priority.
1) The first polling clock cycle, a gets authorization because a corresponds to 0. When A has obtained authorization, A corresponds to 2, B corresponds to 0, and C corresponds to 1.
2) On the second polling clock cycle, B gets authorized because B corresponds to 0. When B has obtained authorization, B corresponds to 2, C corresponds to 0, and A corresponds to 1.
3) On the third polling clock cycle, C gets authorized because C corresponds to 0. When C has obtained authorization, C corresponds to 2, A corresponds to 0, and B corresponds to 1.
A. b, C the priority order is continually reciprocated by the above rule. The algorithm, in combination with time division multiplexing, can evolve as a time slice based poll arbiter. The main disadvantage of the poll arbiter is that the probability of being granted for each master under the algorithm is equal and does not reflect the grant of each host over a period of time.
Disclosure of Invention
Based on this, it is necessary to provide a dynamic lottery bus arbitration method and arbiter based on history adaptation in order to solve the above technical problems.
A dynamic lottery bus arbitration method based on history self-adaption comprises the following steps:
And determining the absolute lottery number of each host according to the static lottery number and the dynamic lottery number of each host, wherein the dynamic lottery number is the authorized number of each host in a preset historical time period.
And carrying out relative processing on the absolute lottery number of each host according to the arbitration application and the absolute lottery number of each host, and calculating the lottery interval section of the relative lottery number of each host on the number axis.
When the bus is transmitting data or the bus is idle, a random number between 0 and 1023 is extracted.
Comparing the interval of the random number on the number axis with the lottery interval on the number axis, and judging the authorized host according to the comparison result, wherein the authorized host obtains the bus use right.
After determining the authorized host, recording the authorization condition of each host in a preset history time period by adopting a shift register, counting the authorization times of each host in the shift register to obtain the number of the dynamic lottery tickets currently owned by each host, and entering the next round of arbitration.
In one embodiment, according to the arbitration application and the absolute lottery number of each host, the absolute lottery number of each host is processed relatively, and the lottery interval section of the relative lottery number of each host on the number axis is calculated, including:
According to the arbitration application and the absolute lottery number of each host, carrying out relative processing on the absolute lottery number of each host to obtain the relative lottery number of each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts.
And carrying out interval processing on the relative lottery number of each host on the number axis, and determining the lottery interval section of each host on the number axis.
In one embodiment, the method for determining the lottery interval of each host on the number axis includes:
Accumulating the relative lottery number of each host on a number axis, wherein the accumulated result of the ith host is as follows:
and the i host is accumulated, i is an integer greater than or equal to 0 and less than the total number of hosts, and the relative_votes [ j ] is the relative lottery number of the j host.
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
In one embodiment, comparing the interval of the random number falling on the number axis with the lottery interval on the number axis, arbitrating the authorized host according to the comparison result, and the authorized host obtaining the bus use right includes:
Comparing the random number with NUM lottery interval sections on the number axis, obtaining the authorized bus by the host corresponding to the lottery interval section where the random number falls, and obtaining the bus use right by the authorized host.
In one embodiment, after determining the authorized hosts, recording the authorization condition of each host in a preset history time period by using a shift register, counting the authorization times of each host in the shift register to obtain the number of dynamic lottery tickets currently owned by each host, and entering the next round of arbitration, wherein the method comprises the following steps:
After the authorized host is determined, when the 1 st round of arbitration is carried out, the ID number of the authorized host is put into the 127 th element space of the shift register, the value of the 0 th element space is moved out, when the 2 nd round of arbitration is carried out, the ID number of the 1 st authorized host is firstly moved to the 126 th element space of the shift register, then the ID number of the 2 nd authorized host is put into the 127 th element space of the shift register, and accordingly, when the 129 th arbitration is carried out, the shift register is continuously moved to the right, and when the 129 th arbitration is carried out, the ID number of the 129 th authorized host is put into the 127 th element space of the shift register, and the ID number of the 1 st authorized host is moved out from the 0 th element space.
Counting the authorized times of each host in the shift register to obtain the number of the dynamic lottery tickets currently owned by each host, and entering the next round of arbitration.
In one embodiment, counting the authorized times of each host in the shift register to obtain the number of dynamic lottery tickets currently owned by each host, and entering the next round of arbitration, including:
Counting the number of times of occurrence of each host ID number of the shift register to obtain the number of the dynamic lottery currently owned by each host, and entering the next round of arbitration.
A dynamic lottery bus arbiter based on history self-adaption comprises a lottery total number calculation module, a lottery management module, a pseudo-random number generation module, a comparison authorization module, a two-dimensional shift register and a dynamic lottery calculation module.
The total lottery number calculating module is used for determining the absolute lottery number of each host according to the static lottery number and the dynamic lottery number of each host, wherein the dynamic lottery number is the authorized number of each host in a preset historical time period.
And the lottery management module is used for carrying out the relativity treatment on the absolute lottery number of each host according to the arbitration application and the absolute lottery number of each host, and calculating the lottery interval section of the relative lottery number of each host on the number axis.
The pseudo-random number generation module is used for extracting a random number between 0 and 1023 when the bus is used for transmitting data or the bus is idle.
And the comparing and authorizing device is used for comparing the interval of the random number falling on the number axis with the lottery interval on the number axis, and judging the host which is authorized according to the comparison result, wherein the host which is authorized obtains the bus use right.
And the two-dimensional shift register is used for recording the authorization condition of each host in a preset historical time period by adopting the shift register after determining the host which is authorized.
The dynamic lottery counting module counts the authorized times of each host in the shift register to obtain the number of the dynamic lottery currently owned by each host, and transmits the number of the dynamic lottery to the lottery total counting module.
In one embodiment, the lottery management module is further configured to perform a relative processing on the absolute number of lottery of each host according to the arbitration application and the absolute number of lottery of each host, so as to obtain the relative number of lottery of each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts.
Accumulating the relative lottery number of each host on a number axis, wherein the accumulated result of the ith host is as follows:
and the i host is accumulated, i is an integer greater than or equal to 0 and less than the total number of hosts, and the relative_votes [ j ] is the relative lottery number of the j host.
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
In one embodiment, the comparing and authorizing device is further configured to compare the random number with the NUM lottery intervals on the number axis, obtain an authorized bus from the host corresponding to the lottery interval where the random number falls, and obtain the bus right from the authorized host.
In one embodiment, the two-dimensional shift register is further configured to, after determining that the authorized host computer is obtained, when the 1 st round of arbitration is performed, place the ID number of the authorized host computer in 127 th element space of the shift register, and move out the value of 0 th element space, when the 2 nd round of arbitration is performed, first move the 1 st authorized host computer ID number to 126 th element space of the shift register, then place the 2 nd authorized host computer ID number in 127 th element space of the shift register, and accordingly, when the arbitration is performed for 129 times, place the 129 th authorized host computer ID number in 127 th element space of the shift register, and move out the 1 st authorized host computer ID number from 0 th element space, count the authorized times of each host computer in the shift register, obtain the number of dynamic lottery tickets currently owned by each host computer, and transmit the number of dynamic lottery tickets to the lottery total number calculation module.
Compared with the traditional fixed arbitration and polling arbitration, the method is mainly improved in that the number of times that each host is authorized in a period of time is counted, the number of times that each host is authorized is increased, the number of dynamic lottery tickets is increased, the host is indicated to be used frequently, the host is authorized for the next time, the number of times that each host is authorized is recorded through a shift register, the authorized condition of each host in a period of time is reflected, the host which the system wants to use next time can be predicted from the probability angle, therefore, the arbiter has self-adaptability and certain predictability, and the characteristics of both the fixed arbiter and the polling arbiter are considered, so that the probability that the host which is used repeatedly for a long time is authorized is high (the characteristic of the fixed arbiter is favored), but the probability that the host which is not used frequently is authorized is not completely excluded (the characteristic of the polling arbiter is favored).
Drawings
FIG. 1 is a flow chart of a dynamic lottery bus arbitration method based on history adaptation in one embodiment;
FIG. 2 is a block diagram of a dynamic lottery bus arbiter based on history adaptation in one embodiment;
FIG. 3 is a schematic diagram of the workflow of a history-based adaptive dynamic lottery bus arbiter in another embodiment.
Detailed Description
The present application will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present application more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the application.
Because the existing arbitration algorithm has a relatively large number of defects, the fixed priority arbitration is considered to be always biased to the host with the highest priority, and the polling arbitration is considered to be the fairness of each host authorization. Therefore, the application provides a dynamic lottery bus arbitration method based on history self-adaption by combining the advantages of the two.
In one embodiment, as shown in fig. 1, a history-based adaptive dynamic lottery bus arbitration method is provided, which includes the steps of:
And 100, determining the absolute number of the lottery tickets of each host according to the number of the static lottery tickets and the number of the dynamic lottery tickets of each host, wherein the number of the dynamic lottery tickets is the authorized number of each host in a preset time period.
Specifically, based on the most recently used principle. The number of times each host is authorized (dynamic lottery number) is counted over a historical period of time. The more times that the host is authorized, the more frequently the host is used, the next time the host is still authorized with a high probability.
In this arbitration algorithm, for a frequently used host, the probability of its re-authorization is high compared to a less frequently used host. This represents a trend in priority to some extent for different hosts. But for a less frequently used host, it is also possible to get grant in the next arbitration, which also characterizes the poll arbiter. Both fixed priority and polling arbiter characteristics are compromised.
Absolute total number of lottery ticket per host = number of dynamic lottery ticket per host + number of static lottery ticket per host.
The static ticket number (static ticket) refers to the number of static tickets each host has and is a configurable parameter. Reflecting the probability that each host may get grant during the initial period of arbitration.
Dynamic ticket number (dynamic ticket) is from two-dimensional shift register, is state quantity, reflects the recent authorization condition of every host, and decides the probability that the host may get authorization next time.
And 102, carrying out relativity treatment on the absolute lottery number of each host according to the arbitration application and the absolute lottery number of each host, and calculating the lottery interval section of the relative lottery number of each host on a numerical axis.
Specifically, the absolute lottery numbers of each host are subjected to a relativity process (after relativity, the sum of the relative lottery numbers owned by all the hosts is 1024), and the lottery interval of each host on the number axis is calculated.
Application number: each host has one bit for application arbitration, all host application bits form req, with bit width of [ NUM-1:0], and req [ i ] represents host number i (so i can be considered as host ID number).
Step 104, when the bus is transmitting data or the bus is idle, a random number between 0 and 1023 is extracted.
Specifically, the method is implemented by using a Linear Feedback Shift Register (LFSR) to extract a random number between 0 and 1023.
And 106, comparing the interval of the random number on the number axis with the lottery interval on the number axis, and judging the host which is authorized according to the comparison result, wherein the host which is authorized obtains the bus use right.
Specifically, the interval in which the random value generated by the pseudo random number falls on the number axis is compared, thereby arbitrating the host that is authorized.
And 108, after the authorized hosts are determined, recording the authorization condition of each host in a preset time period by adopting a shift register, counting the authorization times of each host in the shift register to obtain the number of the dynamic lottery tickets currently owned by each host, and entering the next round of arbitration.
Specifically, the history self-adaption-based lottery bus arbitration method records the authorized times of each host through the shift register, reflects the authorized conditions of each host in a period of history time, and can predict the host which the system wants to use next time from the probability angle, so that the arbiter has self-adaption and certain predictability.
The shift register is used for recording the authorization condition of each host computer 128 times recently. The authorized host ID number is placed in the corresponding element space.
Compared with the traditional fixed arbitration and polling arbitration, the history self-adaptive dynamic lottery bus arbitration method has the main improvements that the number of times that each host is authorized in a period of time is counted, the number of times that each host is authorized is increased, the number of dynamic lottery is increased, the host is indicated to be frequently used, the host is authorized for the next time, the number of times that each host is authorized is recorded through a shift register, the situation that each host is authorized for a period of time is reflected, the host which the system wants to use next time can be predicted from the probability angle, therefore, the arbiter has self-adaptability and certain predictability, the characteristics of both the fixed arbiter and the polling arbiter are considered, the probability that the host which is used for a long time for many times is high (the characteristic of the fixed arbiter is favored), and the probability that the host which is not frequently used for obtaining the authorization (the characteristic of the polling arbiter is favored) is not completely excluded.
In one embodiment, step 102 includes performing a relativity process on the absolute lottery number of each host according to the arbitration request and the absolute lottery number of each host, so as to obtain the relative lottery number of each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts.
And carrying out interval processing on the relative lottery number of each host on the number axis, and determining the lottery interval section of each host on the number axis.
In one embodiment, the interval processing of the relative lottery number of each host on the number axis is performed to determine the lottery interval of each host on the number axis, which includes performing the accumulation processing of the relative lottery number of each host on the number axis, wherein the accumulated result of the ith host is:
and the i host is accumulated, i is an integer greater than or equal to 0 and less than the total number of hosts, and the relative_votes [ j ] is the relative lottery number of the j host.
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
In one embodiment, step 106 includes comparing the random number with NUM lottery intervals on the number axis, obtaining an authorized bus from the host corresponding to the lottery interval where the random number falls, and obtaining the bus usage right from the authorized host.
In one embodiment, step 108 includes, after determining that the authorized host is obtained, when the 1 st round of arbitration, placing the ID number of the authorized host into the 127 th element space of the shift register, shifting the value of the 0 th element space, when the 2 nd round of arbitration, firstly moving the 1 st authorized host ID number into the 126 th element space of the shift register, then placing the 2 nd authorized host ID number into the 127 th element space of the shift register, and accordingly, when the 129 th round of arbitration occurs, the shift register continuously moves right, when the 129 th round of arbitration occurs, placing the 129 th authorized host ID number into the 127 th element space of the shift register, shifting the 1 st authorized host ID number out of the 0 th element space, counting the authorization times of each host in the shift register, obtaining the current owned dynamic lottery number of each host, and entering the next round of arbitration.
In one embodiment, counting the authorized times of each host in the shift register to obtain the number of the dynamic lottery currently owned by each host, and performing the next round of arbitration includes counting the number of occurrences of each host ID number in the shift register to obtain the number of the dynamic lottery currently owned by each host, and performing the next round of arbitration.
It should be understood that, although the steps in the flowchart of fig. 1 are shown in sequence as indicated by the arrows, the steps are not necessarily performed in sequence as indicated by the arrows. The steps are not strictly limited to the order of execution unless explicitly recited herein, and the steps may be executed in other orders. Moreover, at least some of the steps in fig. 1 may include multiple sub-steps or stages that are not necessarily performed at the same time, but may be performed at different times, nor do the order in which the sub-steps or stages are performed necessarily performed in sequence, but may be performed alternately or alternately with at least a portion of other steps or sub-steps of other steps.
In one embodiment, as shown in FIG. 2, a history-based adaptive dynamic lottery bus arbiter is provided, which includes a lottery total calculation module, a lottery management module, a pseudo-random number generation module, a comparison authorization module, a two-dimensional shift register, and a dynamic lottery calculation module.
The total lottery number calculating module is used for determining the absolute lottery number of each host according to the static lottery number and the dynamic lottery number of each host, wherein the dynamic lottery number is the authorized number of each host in a preset time period.
And the lottery management module is used for carrying out the relativity treatment on the absolute lottery number of each host according to the arbitration application and the absolute lottery number of each host, and calculating the lottery interval section of the relative lottery number of each host on the number axis.
The pseudo-random number generation module is used for extracting a random number between 0 and 1023 when the bus is used for transmitting data or the bus is idle.
And the comparing and authorizing device is used for comparing the interval of the random number falling on the number axis with the lottery interval on the number axis, and judging the host which is authorized according to the comparison result, wherein the host which is authorized obtains the bus use right.
And the two-dimensional shift register is used for recording the authorization condition of each host in a preset time period by adopting the shift register after determining the authorized host.
The dynamic lottery counting module counts the authorized times of each host in the shift register to obtain the number of the dynamic lottery currently owned by each host, and transmits the number of the dynamic lottery to the lottery total counting module.
In one embodiment, the lottery management module is further configured to perform a relative processing on the absolute number of lottery of each host according to the arbitration application and the absolute number of lottery of each host, so as to obtain the relative number of lottery of each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts.
Accumulating the relative lottery number of each host on a number axis, wherein the accumulated result of the ith host is as follows:
and the i host is accumulated, i is an integer greater than or equal to 0 and less than the total number of hosts, and the relative_votes [ j ] is the relative lottery number of the j host.
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
In one embodiment, the comparing and authorizing device is further configured to compare the random number with the NUM lottery intervals on the number axis, obtain an authorized bus from the host corresponding to the lottery interval where the random number falls, and obtain the bus right from the authorized host.
In one embodiment, the two-dimensional shift register is further configured to, after determining that the authorized host computer is obtained, when the 1 st round of arbitration is performed, place the ID number of the authorized host computer in 127 th element space of the shift register, and move out the value of 0 th element space, when the 2 nd round of arbitration is performed, first move the 1 st authorized host computer ID number to 126 th element space of the shift register, then place the 2 nd authorized host computer ID number in 127 th element space of the shift register, and accordingly, when the arbitration is performed for 129 times, place the 129 th authorized host computer ID number in 127 th element space of the shift register, and move out the 1 st authorized host computer ID number from 0 th element space, count the authorized times of each host computer in the shift register, obtain the number of dynamic lottery tickets currently owned by each host computer, and transmit the number of dynamic lottery tickets to the lottery total number calculation module.
For specific limitations on the history-based adaptive dynamic lottery bus arbiter, reference may be made to the above limitation on the history-based adaptive dynamic lottery bus arbitration method, and no further description is given here. The various modules in the history-based adaptive dynamic lottery bus arbiter described above may be implemented in whole or in part in software, hardware, and combinations thereof. The above modules may be embedded in hardware or may be independent of a processor in the computer device, or may be stored in software in a memory in the computer device, so that the processor may call and execute operations corresponding to the above modules.
In one embodiment, the history-based adaptive lottery bus arbiter workflow is shown in fig. 3, and the parameters involved in fig. 2 are described as follows:
(1) NUM refers to the total number of hosts, and each host occupies one bit, and 1bit of all hosts is spelled into req, i.e. the bit width of req is [ NUM-1:0], the 0 th bit of req corresponds to host No. 0, and the (NUM-1) bit corresponds to host No. (NUM-1). There are 2 main parameters, i.e., 1bit bus grant application bit, and 32bit absolute lottery total dynsta num, entered into the lottery manager lottary manager by each host. The absolute lottery total dyn_sta_num is defined as a two-dimensional array, [31:0] dyn_sta_num [ NUM-1:0], with each element in the array corresponding to a host 0 to a host (NUM-1).
(2) The absolute lottery total is equal to the static lottery number plus the dynamic lottery total. Namely dyn_sta_num [ i ] =static_ticket [ i ] +dynamic_ticket [ i ].
(3) The two-dimensional shift register is defined as [ log2 (NUM) +1:0] shift_register [127:0], i.e., the depth of the register is 128, each element space is used to store a recently authorized host ID number. After the two-dimensional shift register is initialized, the value of each element is all 1, which represents an invalid host ID number.
The main algorithm steps include:
(B1) If the reset initialization is carried out, the initial value of the absolute lottery number dyn_sta_num [ i ] of each host is equal to the static lottery number static_ticket [ i ] corresponding to the initial value. If not, each host absolute lottery number dyn_sta_num [ i ] is equal to the result of the lottery total number calculator (lottery total calculator) after the last arbitration.
(B2) The absolute lottery number owned by each host is processed relatively:
the absolute numbers of all host lottery tickets are calculated by using the formula:
the relative lottery numbers of each host are calculated by using the formula:
Note that (a) for the same host, if it req i=0, it has a relative lottery number of 0, so that it has no interval on the number axis in the following.
(B) If req [ i ] =1, the relative ticket number= (absolute ticket number of the host/total ticket number of all hosts) ×the total ticket number after the relative (i.e. 1024 tickets).
(B3) Each host computer has relative lottery ticket number (relative_votes [ i ]) and carries out interval processing on the number axis:
① The relative lottery number possessed by each host is accumulated on the number axis as follows:
s[0]=relative_votes[0];
s[1]=relative_votes[0]+relative_votes[1];
s[2]=relative_votes[0]+relative_votes[1]+relative_votes[2];
② The relative lottery ticket quantity of each host machine is processed in intervals on the number axis, and the method comprises the following steps:
(B4) When the bus is used by a host or the bus is idle, the pseudo-random number generator extracts a random number between 0 and 1023.
(B5) And judging in real time which section (section_0, section_i, section_num-1) the random number falls in, and enabling a corresponding host of the section in which the random number falls to obtain authorization.
(B6) Suppose that host number k gets granted use of the bus (grant k=1).
(B7) After the k host is authorized, the following two branches are respectively executed:
and (B7-1 a) shifting the shift register to the left once, storing the host ID number which is authorized at this time into the 127 th element space of the shift register, and shifting out the value of the 0 th element space.
And (B7-1B) counting the occurrence times of the ID numbers of the hosts of the shift register to obtain the dynamic ticket number dynamic_ticket [ i ] of each host.
(B7-1 c) adding the number of static lottery tickets and the number of dynamic lottery tickets for each host to obtain the absolute number of lottery tickets for each host. Namely dyn_sta_num [ i ] =static_ticket [ i ] +dynamic_ticket [ i ].
(B7-2) if the authorized host k finishes the bus, if not, continuing to obtain the bus use right. If the use is finished, the pseudo-random number generator is informed to extract the next random number.
The technical features of the above embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.
The above examples merely represent a few embodiments of the present application, which are described in more detail and are not to be construed as limiting the scope of the present application. It should be noted that it will be apparent to those skilled in the art that several variations and modifications can be made without departing from the spirit of the application, which are all within the scope of the application. Accordingly, the scope of the application should be assessed as that of the appended claims.

Claims (10)

1. A history-adaptive-based dynamic lottery bus arbitration method, comprising:
Determining the absolute lottery number of each host according to the static lottery number and the dynamic lottery number of each host, wherein the dynamic lottery number is the authorization times of each host in a preset historical time period;
According to the arbitration application and the absolute lottery number of each host, carrying out relative processing on the absolute lottery number of each host, and calculating a lottery interval section of the relative lottery number of each host on a number axis;
When the bus is used for sending data or is idle, a random number between 0 and 1023 is extracted;
Comparing the interval of the random number on the number axis with the lottery interval on the number axis, judging the host which is authorized according to the comparison result, and obtaining the bus use right by the host which is authorized;
After determining the authorized host, recording the authorization condition of each host in a preset history time period by adopting a shift register, counting the authorization times of each host in the shift register to obtain the number of the dynamic lottery tickets currently owned by each host, and entering the next round of arbitration.
2. The method of claim 1, wherein the performing the relativity process on the absolute lottery number of each host according to the arbitration request and the absolute lottery number of each host, and calculating the lottery interval of the relative lottery number of each host on the number axis, comprises:
According to the arbitration application and the absolute lottery number of each host, carrying out relative processing on the absolute lottery number of each host to obtain the relative lottery number of each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts;
And carrying out interval processing on the relative lottery number of each host on the number axis, and determining the lottery interval section of each host on the number axis.
3. The method of claim 2, wherein the step of compartmentalizing the relative lottery numbers of each host on the number axis to determine the lottery interval for each host on the number axis comprises:
Accumulating the relative lottery number of each host on a number axis, wherein the accumulated result of the ith host is as follows:
wherein, s [ i ] is the accumulated processing result of the ith host computer, i is an integer greater than or equal to 0 and less than the total number of the host computers, and relative_votes [ j ] is the relative lottery number of the jth host computer;
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
4. The method of claim 1, wherein comparing the interval in which the random number falls on the number axis with the lottery interval in the number axis, arbitrating the authorized host based on the comparison, the authorized host obtaining the bus usage rights, comprising:
Comparing the random number with NUM lottery interval sections on the number axis, and obtaining the authorized use bus by a host corresponding to the lottery interval section where the random number is located;
The authorized host obtains bus usage rights.
5. The method of claim 1, wherein after determining the authorized hosts, using the shift register to record the authorization status of each host in a preset history period, counting the authorization times of each host in the shift register to obtain the number of dynamic lottery currently owned by each host, and entering the next round of arbitration, wherein the method comprises the steps of:
When the round of arbitration is 2, firstly moving the ID number of the host authorized for 1 time to the 126 th element space of the shift register, then putting the ID number of the host authorized for 2 times to the 127 th element space of the shift register, and accordingly, when arbitration happens for 129 times, putting the ID number of the host authorized for 129 times to the 127 th element space of the shift register and moving the ID number of the host authorized for 1 time from the 0 th element space;
counting the authorized times of each host in the shift register to obtain the number of the dynamic lottery tickets currently owned by each host, and entering the next round of arbitration.
6. The method of claim 5, wherein counting the number of grants for each host in the shift register to obtain the number of dynamic tickets currently owned by each host, and entering the next round of arbitration, comprises:
Counting the number of times of occurrence of each host ID number of the shift register to obtain the number of the dynamic lottery currently owned by each host, and entering the next round of arbitration.
7. The history self-adaption-based dynamic lottery bus arbiter is characterized by comprising a lottery total number calculation module, a lottery management module, a pseudo-random number generation module, a comparison authorization module, a two-dimensional shift register and a dynamic lottery calculation module;
The total lottery number calculation module is used for determining the absolute lottery number of each host according to the static lottery number and the dynamic lottery number of each host, wherein the dynamic lottery number is the authorized number of each host in a preset historical time period;
The lottery management module is used for carrying out relative processing on the absolute lottery number of each host according to the arbitration application and the absolute lottery number of each host, and calculating a lottery interval section of the relative lottery number of each host on a number axis;
The pseudo-random number generation module is used for extracting a random number between 0 and 1023 when the bus is used for sending data or the bus is idle;
The comparing and authorizing device is used for comparing the interval of the random number falling on the number axis with the lottery interval section on the number axis, judging the host which is authorized according to the comparison result, and obtaining the bus use right by the host which is authorized;
The two-dimensional shift register is used for recording the authorization condition of each host in a preset historical time period by adopting the shift register after determining the host which is authorized;
And the dynamic lottery counting module counts the authorized times of each host in the shift register to obtain the number of the dynamic lottery currently owned by each host, and transmits the number of the dynamic lottery to the lottery total counting module.
8. The arbiter of claim 7, wherein the lottery management module is further configured to perform a relativity process on the absolute number of lottery for each host according to the arbitration request and the absolute number of lottery for each host, to obtain the relative number of lottery for each host as follows:
Wherein dyn_sta_num [ i ] is the absolute lottery number of the ith host, req [ i ] is the arbitration application of the ith host, relative_votes [ i ] is the relative lottery number of the ith host, total is the absolute lottery total number of all hosts, and NUM is the number of hosts;
Accumulating the relative lottery number of each host on a number axis, wherein the accumulated result of the ith host is as follows:
wherein, the ith host is accumulated to obtain the accumulated result, i is an integer greater than or equal to 0 and less than the total number of hosts, and the relative_votes [ j ] is the relative lottery number of the jth host;
According to the obtained accumulated processing result, the relative lottery quantity of each host machine is divided into intervals on the number axis to obtain lottery interval of each host machine on the number axis, wherein the lottery interval of the first host machine is [0, s 0], the lottery interval of the second host machine is [ s0, s 1], the lottery interval of the second host machine is [ s1, s 2], and so on, the lottery interval of the NUM host machine is [ s NUM-2, s NUM-1 ].
9. The arbiter of claim 7, wherein the compare and grant is further configured to compare the random number with NUM lottery intervals on a number axis, obtain a grant bus from a host corresponding to the lottery interval in which the random number falls, and obtain a bus usage right from the granted host.
10. The arbiter of claim 7, wherein the two-dimensional shift register is further configured to, after determining that the authorized host is in the shift register, place the authorized host ID number in the shift register 127 th element space and move the value of the 0 th element space when the authorized host is in round 1, move the 1 st authorized host ID number in the shift register 126 th element space when the authorized host is in round 2, place the 2 nd authorized host ID number in the shift register 127 th element space, and accordingly, the shift register is continuously moved to the right when the authorized host is in round 129, place the 129 th authorized host ID number in the shift register 127 th element space when the authorized host is in round 129, and move the 1 st authorized host ID number out of the 0 th element space, count the authorized numbers of each host in the shift register, obtain the number of dynamic lottery tickets currently owned by each host, and transmit the number of dynamic lottery tickets to the total number calculation module.
CN202411194173.1A 2024-08-28 2024-08-28 Dynamic lottery bus arbitration method and arbitrator based on history adaptation Pending CN119046205A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202411194173.1A CN119046205A (en) 2024-08-28 2024-08-28 Dynamic lottery bus arbitration method and arbitrator based on history adaptation

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202411194173.1A CN119046205A (en) 2024-08-28 2024-08-28 Dynamic lottery bus arbitration method and arbitrator based on history adaptation

Publications (1)

Publication Number Publication Date
CN119046205A true CN119046205A (en) 2024-11-29

Family

ID=93581302

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202411194173.1A Pending CN119046205A (en) 2024-08-28 2024-08-28 Dynamic lottery bus arbitration method and arbitrator based on history adaptation

Country Status (1)

Country Link
CN (1) CN119046205A (en)

Similar Documents

Publication Publication Date Title
Wu et al. Worst case analysis of DRAM latency in multi-requestor systems
US6009275A (en) Centralized management of resources shared by multiple processing units
US20080288689A1 (en) Opportunistic granting arbitration scheme for fixed priority grant counter based arbiter
CN105389211B (en) Memory allocation method and delay perception-Memory Allocation device suitable for NUMA architecture
KR19980081352A (en) Method and system for controlling access to shared resources in data processing system
US20040059879A1 (en) Access priority protocol for computer system
US20060095634A1 (en) Method and apparatus for round robin resource arbitration with a fast request to grant response
US7350003B2 (en) Method, system, and apparatus for an adaptive weighted arbiter
CN101145140A (en) A Dynamic Adaptive Bus Arbiter Based on On-Chip Multiprocessor System
CN116627870A (en) Dynamic priority weighted polling arbitration method and arbiter
US10289331B2 (en) Acceleration and dynamic allocation of random data bandwidth in multi-core processors
CN115454897A (en) Method for improving arbitration mechanism of processor bus
Mirosanlou et al. Parallelism-Aware High-Performance Cache Coherence with Tight Latency Bounds
CN119046205A (en) Dynamic lottery bus arbitration method and arbitrator based on history adaptation
Gupta et al. Efficient bus arbitration protocol for SoC design
CN105824769B (en) A kind of configurable dynamic time piece robin scheduling method
KR100973419B1 (en) Bus Arbitration Method and Device
El-Kustaban et al. A Bus Arbitration Scheme with an Efficient Utilization and Distribution
CN1326047C (en) Method of arbitration which allows requestors from multiple frequency domains
Bajaj et al. Arbitration schemes for multiprocessor Shared Bus
Modi et al. CABARRE: Request response arbitration for shared cache management
Agrawal et al. Virtually pipelined network memory
Doifode et al. Dynamic lottery bus arbiter for shared bus system on chip: a design approach with VHDL
CN119046206A (en) Dynamic lottery bus arbitration method and arbiter based on difference weighting
Chang et al. On deadlock problem of on-chip buses supporting out-of-order transactions

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination