Note: Descriptions are shown in the official language in which they were submitted.
~UAL ~C~ESS BVS AR~IT-R
sackground of the Invention
-
This invention relates generally to digital systerns a~d
in particular to systems comprising a plurality of devices
interconnected by a common bus having a bus arbiter for deter-
mining which one of the devices shall have first access to the
common bus when more than one device is requesting use thereof.
T;~e devices may be processors, memories and~or input-output
controllers.
Bus arbitration is generally accomplished by distributed
or centralized arbitration techniques. In a distributed arbi-
tration system each of the devices connected to the common
bus comprises an arbitration network as described in a patent
to Evett, U.S. Patent No. 4,402,040 which is assigned to the
same assignee as the present invention. In such a distributed
arbitration system, the arbitration network in each device
determines the device's priority relative to other devices
based on a code generated by each device. This approach is
often used in high reliability or fault-tolerant systems
where single point failures cannot be tolerated. In a cen--
tralized arbitration system, a single bus arbiter determines
which one of a plurality of devices will be granted access
to a common bus based on assigned priority to each device.
~owever, if one or two of the higher priority devices monopo-
lize the bus, then lower priority devices are prevented from
~2'~ 3
ever using it. Thus,.there is a n~ed for a '~us a-biter thz~
~7ill allow all devices to have ~n equaliz~d op?or-l~nity to
have common bus access.
--2--
::~2~
52gOl-673
~ y~ he Inventlon
In accordance with the present inven-tion a bus arbiter
is provided for de~ermir.lng whlch one of a plu~ality of devices
interconnected by a common hus has prioxlty ~or obtalning access
to the hus and further insures tha~ each of the devices ~7ill
obtain periodic aecess to the bus. In response to a series of
sampling signals bus access requests generated by the devices are
sampled and stored. The requesting devices are granted access to
the bus in aceordance with a predetermined prlority. However,
each of the requesting devices is granted access to the bus prior
to the occurrence of the next succeediny sampling siynal. In this
manner equal access to the bus is obtained for all of the devices.
The invention may be summarized, according to one broad
~spect, as in combination: a plurality of devices operating
asynchronously; a bus means for interconnecting sald plurality of
devices; bus arbiter means coupled to each of said devices for
determining which one of said devices, during a sampling period
controlled by a continuous clock signal, has priority for
obtaining access to said hus and generating bus grant signals,
~0 said priority determining means providing an equal opportunity for
each of said devices to obtaln access to said bus in response to
each one oi a series of sampling signals for sampling bus access
requests generated by sald devices within said period, said
sampling signals being generated within said priority determining
means; and said bus arbiter meanfi comprising timing means
controlled by said clock signal for synchronizing said bu6 accefis
62~01-67
grant signals coupled to said plurality of devlce3.
According to another broad aspect, the inventior may be
summarized as the method of providing a plurallty of
asynchronously operatlng devices with prioritized, equal access to
a common bus of a dlgital system compris:Lng the s~eps of, sampling
and storing bus request signals from ~aid devices in response ~o
each one of a series of sampliny slynals generated in accordance
with a continuous clock slgnal; converting said bus request
signals into a priority sequence of bus granting signals, said bus
request signals being sampled and stored by said sampling and
storing means in response to one of the sampling signals in said
series of sampling signals; producing sai~ series of sampling
signals in accordance with said clock signal, each of said
sampling signals in said series of sampling signals being produced
after said converting means converts said sampled and stored bus
request signals into said priority sequence of bus granting
signals; and synchronizing said sequence of prioritized bus
granting signals coupled to said plurality of devices in
accordance with said clock signal.
Brief Description of the Dra~,lings
__ _ _
The ahove-mentioned aspects and other features o'
the inventioll are explained more fully in the 'ollo~,/ing
description taken in connection ~1ith the accompanying
drawings, ln which:
FIG. 1 is a functional block diagram of a com~uter
system comprising a plurality of devices interconnected by
a common bus and having a bus arbiter for determining
device access to the common bus;
FIG. 2 shows a bus clock and bus arbiter timing events
- occuring at various transitions OL the bus clocX;
FIG. 3 is a block diagram ofLa bus request gate of the
invention employing programmable array logic;
FIG. 4 is a block diagram of a bus request memory of
the invention;
FIG. S is a block diagram of a priority resolver of
the invention;
FIG. 6 is a block diagram of a bus grantor synchronizer
of the invention;
FIG. 7 is a block diagram of a bus access control logic
of the invention employing programmable array logic;
FIG. 8 is a block diagram of a bus request reset logic
of the invention employing programmable array logic;
FIG. 9A is a typical com'~inational logic diagram; and
FIG. 9B is a programmable array logic equivalent diagram
for the logic diagram sho~ln in FIG. 9A.
--S--
Descri~tion of the P~eferred Embodi~ent
_ _ __ __ _ .
?~eferring first to FIG. l, there is shown a bloc~.
diagram of a genera]ized computer syste,n 50 comprising a plu-
rality of devices including I/O controllers 5-10, ~rocessors
; 11-15, and memories 16-20. These devices are interconnected
by a common bus 22 and coupled to each of the plurality OL
devices 5-20 is a bus arbiter 24 for determining the priority
of device access to the common bus 22 during a series of
sample periods. The bus a-biter 24 provides an equal oppor-
tunity for each of the devices 5-20 to gain access to the
common bus 22 in accordance with bus request signals 40l-40l6
generated by each of the devices 5-20 an~ fed to the bus
arbiter 24 where they are converted into a sequence of bus
priority grant signals 441-4416. The number of devices 5-20
lS in computer system 50 is somewhat arbitrary; however, in the
preferred embodiment shown in FIG. 1, the bus arbiter 24 has
been designed to handle a total of 16 bus requests from 16
devices which may be any combination of the I/O controllers
5-10, processors 11-15, and memories 16-20.
The bus arbiter 24 as shown in FIG. l determines the
~rlority order in which the plurality o devices 5-2~ inter-
connected by common bus 22 will gain access to the bus 22
during each one of the series of sample periods, and also
oermits each one of said devices 5-20 to have an equal
opportunity with respect to the other devices for bus access
by virtue of the series of sam~le periods. ~us arbiter 24
comprises a sample and store 27 network whicrl receives up to
16 bus request sisnals 401-4016 from any combination of the
devices 5-20 connected to bus 22. The sam21e and store 27
network comprises a bus request gate 28 coupled to a bus
request memory 30 for storage of said bus requests signals
401-4016 upon the occurrence of one of a series of sample or
enable signals 42. A priority resolver 32 coupled to the
outputs of bus request memory 30 converts the bus requests
signals 4nl-4016 which are sampled by the series of enable
signals 42 into a sequence of bus grant signals 481-488.
Priority resolver 32 determines which one of the stored or
latched bus requests 461-4616 has the highest priority and
generates the sequence of bus grant signals 481-4816 to the
bus grantor synchronizer 34 (and to the bus request reset
26) in accordance with the priority established for each of
the latched bus requests 461-4616. The bus grantor synchron-
izer 34 generates bus priority grant signals 441-4416 which
are synchronized with the bus clock 38 and sent to the device
having the highest priority of all the devices 5-20 requesting
access to bus 22 that were sampled and stored in the bus
request memory 30. The bus clock 38 is coupled from co~mon
bus 22 to the bus request gate 2~ and bus access enable 36.
In the bus access enable 36, the hus clock 3~ is gated by
the enable signal 42 forming the gated clock signal 4~ which
--7--
iS used to s -nchronize the bus ~rlority gran~ signals 441-4~16
or eac'n o~ .he devices 5-20. ~he enable sisnal 42, generated
by the bus access enable 36, clocks a new set o~ bus requests
signals 401-4016 into the bus request ,~emory 30 after all
previous bus requests stored in said ~lemory 30 ha~e been
processed. :~;onitoring the latched bus request signals 461-
4616 from the bus request memory 30 determines when all of
~he previously stored bus requests 40l-4016 have been pro-
cessed. The bus grant signals 481-48l6 generated by the
priority resolver 32 are coupled to a bus request reset 26
which also receives the bus requests signals 40l-40l6.
The bus request reset 26 generates one of the reset signals
27l-27l6 for one of the storage elements in the bus request
memory 30 after a device which generated the corres?onding
l~ one of the bus requests 40l-40l6 stored in said memory 30
has been granted access to the bus 22. The resetting of the
most recently processed one of the latched bus requests
46l-4616 enables the priority resolver 32 to determine
which one of the remaining stored bus requests 46l-46l6 in
3~
the bus request memory ~ should be processed next based on
a preferred prioriiy order, or if the bus request memory 30
is empty, the bus access enable 36 permits the sampling of a
new set of bus requests 401-40l6 for storage in bus request
memory 3 0 .
2~ Referring now to FIG. 2, the bus clock 38 signal is
sho~n along ~ith timing events ~eing no~ed at the variolls
transitions of the bus clock 3~. ht ~ime Tl, any activP
bus requests 401-40~6 are gated into the b s request memory
30 by the enable signal 42. At time T~, the latched bus
requests signals 461~46l6 are coupled to the priority resolver
32 which proceeds to determine the highest priority device
requesting access to bus 22. This priority determination
takes place between T2 and T3 resulting in the generation
of one of the bus grant signals 431-4816 which is coupled
to the bus grantor synchronizer 34. At time T4, one of the
bus priority grant signals 441-k4l6 is generated and sent
to the device currently having the highest priority for
obtaining bus 22 access.
Some of the logic used to implement the functions o the
bus arbiter 24 as shown in FIG. 1., utilizes programmable
array logic such as that developed by Monolithic Memories,
Inc., of Santa Clara, CA 95050. Programmable array logic may
efficiently solve system partitioning and interface problems
brought about by increases in semiconductor device technology,
and it is an extension of the 'usible link technology used in
a bipolar programmable read-only memory (PROM). The fusible
link PROM first provided the capability to "write on silicon."
In a few seconds, a blank PROt~ is transferred from a general
purpose device into one containing a custom algorithm, micro-
program, or Boolean transfer function. ~his has opened up
nc;~ horizors for the use of ?~'s in co~ u~er controlled
stores, character generators, da~a storage tab1es and many
other applications~ The key ~o ~he PRO~'s success is that
it allows the designer to quickl~ and easily customize the
chip to fit his unique requiremen~s. ~rogrammed array loglc
extends this progra~mable flexibility by utilizing fusible
lin~ .echnology to implement logic func.ions such as custom
logic varying in complexity from random gates to comDlex
arithmetic functions. Further details of a program.ned array
logic concept are described in the Programmed Array Logic
~andbook, 3rd edition, by r~onolithic ~emories, Inc., of
Santa Clara, CA 95050.
Programmed array logic implements the familiar sum of
products logic by using a progra~mable AND array whose output
terms feed a fixed OR array. Since the sum of products formed
can express any Boolean transfer function, the programmed
array logic circuit uses are only limited by the number of
terms available in the AND-OR arrays. Programmed array logic
devices may be procured in different sizes to allow for
effective logic optimization and are fully described in the
above-referenced Handbook.
Referring now to FIG. 9A, there is shown a normal
combinatorial logic diagram for the following function:
Output = IlI2 ~ 2
FIG. 9~ shows a programmed array logic equivalent for this
--10--
tralsfer funct.on. The "~" represents an intact fuse used
t- _er~orm the logic AiD function; hs"ever, the in3llt ter s
on ~he common line with the ~'s are not connected together.
mhe ?rogrammable array logic de~tices are programmed using
; inexpensive conventional PRO~I programmers with appropriate
personality and socket adapter cards.
The first step in designing a programmed array logic
dev-ce is selecting the pinout by examining the random logic
o be re?laced with a devise function. The next step is to
~ri~e the Boolean logic equations ~in surn of products form)
which ~ill transform tne in?uts into the desired outputs.
These explicit logic equations specify the design of a pro-
grammed array logic device precisely, and they are easily
simulated and edited. Tables 1-7 show the Boolean logic
equations for the programmed array logic required to implement
the logic design of bus arbiter 24. By using PALASM from
Monolithic Memories, Inc., which is a Fortran IV program for
assembling the programmed array logic design specification
and translating the logic equation to a fuse pattern, the
process of designing a custom chip is automatically accom-
?lished. PALASM also contains a simulator which exercises
runction Table vectors in the logic equations. Inconsis-
tencies between the vectors and the equations are reported
as errors. The simulator also translates a function table
2~ vQctors to a set of universa]. test vectors which may be used
--11--
'or unction51 tes.ing after the programmed array logl~
device is favricated.
Referring again to Tables 1-7 and in particular to
Table 3 wnich specifies the programmed a~ray logic for gen-
erating a portion of the reset signals 271-2716 for resetting
the latched b~s requests signals 461-4616. The first logic
equation for generating RESE~l is as follows:
RESETl=BGRNTl*/BREQl+IMIT+P,~RON
This logic equa~ion states that the P~ESETl signal is genera~ed
i-^, and only if, a bus grant signal (BGRNTl) e~ists when a
bus reques~ (a2EQl) signal does not exist, or power has been
turned on (PW~ON) or an initialize signal (I~IIT) exists from
a remote location. The remaining logic equations are simi-
larly interpreted and by virtue of the chosen acronyms are
essentially sel.-identifiable. In tables 7 and 8, the "IF"
equation indicates that if any of the latched bus requests
signals (L3REQl to LBREQ16) are active, then the respective
outputs (A1.lYOl to ANY16) will be brought from a voltage
level to a GROUND level. ~herefore, the enable signal 42 zs
shown in FIG. 7 will be generated only when there are no
active latched bus requests signals 461-4616.
Referring now to FIG. 3, two programmed array logic
devices, P.~L01 52 and PAL02 54, are used to i~plement the
combinational logic required for generating the gated bus
2; requests signals 561-561~. PAL01 52 handles eight of the bus
-12~
requests 401-408 and PAL02 54 handles the other eigr.t of the
bus requests 409-4016 in conjunction with bus clock 38 and
enable signal 42 as specified by the logic equations shown
in Tables 1 and 2. PAL01 52 and ~AI,02 54 generate one or
~ore of the gated hus requests signals 561-5616 (depending
on the number of devices 5-20 seeking bus access) for storing
in the bus request ~èmory 30.
~eferring now to ~IG. 4, there is shown a plurality of
QUAD SR (SET-RESET) flip-flops 60-66 for providing storage
for the gated bus request signals 561-5616. Each SR flip-
Llop 60-66 may be embodied by a Texas Instrument (TI) 74LS279
Quad SR flip-flop integrated circuit (IC), which provides
Cour storage locations per IC. Each gated bus requests
561-5616 signal has a storage location assigned to it within
one of the SR flip-flops 60-66. Whenever there is a request
from more than one device connected to bus 22, wanting access
to bus 22 by generating the bus request signals 401-4016,
priority resolver 32 converts the latched bus requests 461-
4616 into a sequence of bus grant signals 481-4816 by deter-
mining the device priority of the latched bus request signals
-4616-
Figure 5 shows the logic devices used to implement the
priority resolver 32 functions. Eight of the latched bus
requests signals 461-468 are coupled to inverter 70 which is
coupled to a 8-3 priority encoder 74 which, in turn, is
-13-
coupled to 3-8 ?riority decoders 78 and ~0, The other eight
latched bus reques.s signals 469-A616 zre cou~led to in,-rter
72 which is co~pled to an 8-3 priority encoder 76, ~he output
of which is coupled to 3-8 priority decoder 30. This net~/ork
of encoders and decoders results in a sequence of the bus
grant signals 481-4816 being generated based on an order of
highest priority for the devices having a latched bus request
signal 461-4616 pending. The inverters 70 and 72 may be
embodied by Texas Instrument 74S04 integrated circuits, the
8-3 priority encoders 74 and 76 may be em~odied by Texas
Instrument 74148 8-to-3 line octal priority encoders. The
3-8 priority decoders 78 and 80 may be embodied by Texas
Instrument 74S138 3-to-8 line decoder/demultiplexer I~.
v\,, w
Referring n~ to FIG. 6, when one of the bus grant signals
481-4816 is generated, it is synchronized with gated clock
~,3
44 using D flip-flops ~ and 84. One of the bus priority
grant signals 441-4416 generated by the bus grantor
synchronizer 34 is coupled to one o the devices 5-20 that
will now be granted bus 22 access. The D flip-flops may be
embodied by Texas Instrument 74S374 octal D type flip-flop
integrated circuits.
Referrlng now to FIG. 7, the bus access enable 36 func-
tional logic is shown. Programmed array logic devices,
PAL07 90 and PAL08 92 implement the logic required to generate
a series of sampling signals in the form of one or more enable
-14-
s s-.ala 42 synchronized with bus clock 38. One o~ aaid enable
signals 42 allows a new pending set of bus requests 401-4015
to 'ae gated and stored in tne bus request memory 30. The
generation o a subsequent one of the sample or enable signals
42 requires that there he no latched bus requests pending
which -ere stored in the bus request memory 30 at the occur-
rence of the previous enable signal 42. In addition, the
gated clock slgnal 45 is generated in sequence with the
ena~le signal 42 via AND gate 96. The logic equations for
~}.L07 90 and PAL08 92 are given in Tables 7 and 8, respectively.
2eferring now to FIG. 8, there is shown the bus request
reset 26 functions which are embodied using four programrned
array logic devices, PAL03, PAL04, PAL05, and PAL06, 100-106
for im~?lementing the combinational logic required to generate
the reset signals 271-2716. Tables 3-6 define the logic equa-
tions for the ?rogrammed array logic devices 100-106 which
generate the reset signals 271-2716. All the reset signals
271-271G reset the corresponding flip-1Op in the bus request
memory 30 if, and only iE, a corresponding bus grant signal
481-4816 exists when a corresponding bus request signal 401-
416 does not exist, power on reset 99 occurs or an initialize
98 signal occurs.
This concludes the Description oE the Preferred
Embodiment. r~o~,~ever, many modifications and alterations
would be obvious to one of ordinary skill in the art without
--15--
2901-673
departing from the spirit and the scope of the inventive concept.
For example, the bus arbiter 24 has been designed to handle bus
requests from sixteen devices connected to bus 22; however, the
bus arbiter 24 could readily be designed to accommodate fewer bus
requests or greater bus requests than the embodiment described
herein. In addition, the bus clock 38 may be provided to bus
arbiter 24 as shown in FIG. 1, or may be generated within the bus
arbiter 24 especially in such an embodiment comprising asynchronous
devices coupled to the common bus. Therefore, it is intended that
the scope of this invention be limited only by the appended claims.
-16-
~$~.
~4~;~3yl
TABLE 1, PP.L01 - GATED Brls R-QUESTS
GREQ1=BREQl*BCLK*E!iAaLE
GRE(,22=B~EQ2*BCLX*Et1A3LE
GREQ3=B?~EQ3*2CLK*ENA3LE
GREQ4=3REQ4*3CI,K*ENABLE
GREQ5-BREQ5*BCLK*E'NABLE
GREQ6=BREQ6*BCLK*ENABLE
GREQ7=BREQ7*BCLK*ENABLE
GREQ8=GREQ8*3CLK*ENABLE
.
TABLE 2, PAL02 - GATED BUS R_QUESTS_
GREQ9=3REQ9*BCLX*ENABLE
GREQ10=BREQ10*BCLK*ENABLE
GREQll=BREQ11*3CLK*ENABLE
GREQ12=BREQ12*BCLK*ENABLE
GREQ13=BREQ13*BCLK*ENABLE
GREQ14=BREQ14*BCLK*ENA~LE
GREQ15=BREQ15*BCLK*E~ABLE
GREQ16=BREQ16*BCLK*ENABLE
TABLE 3, PAL03 - LATCHED BUS REQUEST RESET
RESETl=BGRNT1*/BREQl+I~IT+PWRON
RESET2=8GRNT2*/BREQ2fINIT+PWRON
RESET,3=BGRNT3*/BREQ3+INIT+PWRON
RESET4=BGRNT4*/BREQ4~I~.iIT+PWRON
TABLE 4, PAL04 - LATCHED BUS REQUEST RESET
RESET5=BGRNT5*/BREQ5+INI'r+PWRON
RESET6=BGRNT6*/BREQ6+INIT+PWRON
RESET7=BGRNT7*/BP~EQ7+INIT+PWRON
RESET8=BGRNT~*/BREQ8+INIT+PWRON
.
-17-
TABLE 5, PAL05 - LATCHED BUS P~EO'UEST ?.ESET
. _ ~ __ _ _ _____ ___ ____
RESET9=BGR~9*/3?_~29+I;`lIT~?~ROr1
RESET10=~GR.~T10*/~REQ10+I'.`~I'r~P~J~
RESE:Tll=3GRNTll*/_REQll`tIrNI'r~P'~RON
RESET12=3GRNL12*/B~EQ12+I,JIT+P~RON
TABLE 6, PAL06 - LATCHED BUS REQUEST RESET,
RESET13=3GRNT13*/3REO13~INITlP~RON
RESET14=BGRNT14*/BRE 14+INIT+PI~RON
~ESET15=BGRNT15*/BREQ15+Il.1IT+P'i~RON
RESET16=BGRNT16*/BREQ16+INIT+PWRON
TABLE 7, PAL07 - ENABLE RECEPTION OF BUS REQUESTS
IF (LBREQl) ANV01 = GROUND
IF (L8REQ2) AN~02 = GROUND
IF (LBREQ3) ANV03 = GROUND
IF (L3REQ4) ANY04 = GROUND
IF (LBREQ5) ANY05 = GROUND
IF (LBREQ6) ANY06 = GROUND
IF (LBREQ7) ANY07 = GROUND
IF (LBREQ8) ANV08 = GROUND
TABLE 8, PAL08 - ENABL~ RECEPTION OF BUS REQUESTS
IF (LBREQ9) ANY09 = GROUND
IF (LBREQ10) ANY10 = GROUND
IF (LBREQll) ANVll = GROU?ID
IF (LBREQ12) ANY12 = GROUND
IF (LBREQ13) A~Y13 = GROUND
IF (LBREQ14) ANY14 = GROUND
IF (LBREQ15) ANY15 = GROU~D
IF (LBREQ16) ANY16 = GROUND
-18-
