Ulllted States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,546,547
`
`Bowes et al.
`
`[45] Date of Patent:
`
`Aug. 13, 1996
`
`||||l|llllllllIll||||||||||||||||||||||l||lllll|||lll|||||||||l||l||l||llll
`US005546547A
`
`[54] MEMORY BUS ARBITER FOR A
`COMPUTER SYSTEM HAVE“; A {)5}:
`
`5313.591
`5,353,417
`
`5:15:94 Averill
`lt}tl994 Fun-co et a].
`
`
`
`395525
`3951325
`
`C0'PR0CE550R
`_
`_
`_
`‘
`_
`I""°“1°’S- ¥1a:dh:"=1B-:5:$:f:)»Dfil"§?'g;E;iF“"d 3-
`
`[751
`
`Primary Examir:er—-Jack B. Harvey
`AssismmExamir1er—David A. Wiley
`Atrorney.Agen1,orFinn—Blal(e1y,Sol<oloff,Taylor&Zaf-
`man
`
`ABSTRACT
`[571
`An arbitration scheme for a computer system in which a
`digital signal processor resides on the computer system's
`memory bus without requiring a block of dedicated static
`random access memo . An arbitration c cle is divided into
`10 slices of which 5 slices are providedyin each arbitration
`loop to the digital signal processor. Two slices are provided
`each to the system’s U0 interface and to the peripheral bus
`controller A final slice is provided to the svstem’s CPU- A
`default state when no memory bus resource is requesting the
`system memory bus parks the memory bus on the CPU. The
`arbitration scheme
`rovides suflicicnt bandwidth for real-
`Lime signal processiiig by the digital signal processor oper-
`ating from the System's dynalnic random access memory
`while also providing sufficient bandwidth for a local area
`network interface through the systcm’s U0 interface.
`
`3 Claims, 5 Drawing Sheets
`
`[73] Assignee: Apple Computer, Inc., Cupertino,
`Cam‘
`
`lzll ADPL N0-3 139:133
`-
`.
`[22] mod‘
`Jam 28' 1994
`G961? 13100
`[5]]
`Int. Cl.”
`........................................... .. 3951994; 395E293
`[52] U.S. Cl.
`[531 Field of Search .................................... .. 395525, 425
`
`References Cited
`U'S' PATENT DOCUMENTS
`2:193? Kncib .................................... .. 395325
`4,641,238
`Stl99O Kitamura at al.
`.. 395K425
`4,923,234
`H1991 Craft at al.
`.. 3951825
`4.987.529
`5,263,163 1l!l993 Holt et al.
`.. 395F325
`5,301,232
`411994 Aminl cl a1. .......................... .. 395325
`
`
`
`[56]
`
`10
`
`200
`
`12
`
`
`CPU W (W
`
`14
`K’
`MAIN MEMORY
`SUBSYSTEM
`
`-420
`
`129
`
`MEMORY BUS
`
`-110
`
`an-
`
`30- CONTROLLER——
`
`
`
`~40
`
`NUBUS
`CONTROLLER
`
`NUBUS
`
`430
`
`131-
`
`COMMUNICATIONS ~132
`
`Page 1 of 25 ZTE EXHIBIT 1003
`Page 1 of 25
`ZTE EXHIBIT 1003
`
`

`
`U.S. Patent
`
`Aug. 13,1996
`
`Sheet 1 of 5
`
`5,546,547
`
`
`MAIN MEMORY
`SUBSYSTEM
`(DRAM)
`
`
`
`MASS
`STORAGE
`
`
`
`
`
`
`
`I-‘tgure 1
`
`(Prior Art )
`
`Page 2 of 25
`Page 2 of 25
`
`

`
`U.S. Patent
`
`Aug. 13, 1996
`
`Sheet 2 of 5
`
`5,546,547
`
`Z
`5
`
`3
`-;
`52|-
`
`5%
`
`_l
`.1]—
`E55
`$n-
`
`3
`"
`
`_
`
`
`
`—|—
`
`§§
`é
`
`RT
`
`{D
`3
`o
`2
`
`14
`
`10
`
`200
`
`12
`
`”é‘I”e3”»«E§‘EI‘4Y
`CPU W <nnAM>
`I
`I
`I
`I
`MEMORY BUS
`
`~1 10
`
`I
`
`I
`
`
`- CONTROLLER
`
`NUBUS
`CONTROLLER
`
`40
`
`|
`NUBUS
`
`~13”
`
`‘I31- VIDEO
`
`COMMUNICATIONS —-132
`
`Figure 2
`
`Page 3 of 25
`Page 3 of 25
`
`

`
`U.S. Patent
`
`Aug. 13, 1996
`
`Sheet 3 of 5
`
`745‘)645,5
`
`Mennui
`
`Page 4 of 25
`Page 4 of 25
`
`

`
`U.S. Patent
`
`Aug. 13, 1996
`
`Sheet 4 of 5
`
`5,546,547
`
`
`
`DSP
`STATE
`
`MACHINE
`
`NON-DSP
`
`STATE
`MACHINES
`NON-DSP
`
`
`BUS INTERFACE
`UNIT
`
`
`
`
`
`BUS ARBTTRATION UN1T
`LOGIC
`
`
`
`
`
`
`
`
`asp
`24“ WATCHDOG
`men
`
`CPU LOCK
`
`Figure 4
`
`Page 5 of 25
`Page 5 of 25
`
`

`
`..lHe4...aPQMU
`
`Aug. 13, 1996
`
`Sheet 5 of 5
`
`5,546,547
`
`Mmuammrfl
`
`asm__._._.mzaoEu
`
`:10m__._._.>mzm>_E
`
`EEEma:5zm_>_mn_
`
`E220mamm=.F9m82%;
`
`229...mamm__._._.mzaohas
`m_m_._..mm_<m_.=>m2m>=.._n_mammx»mzaonag
`
`mamwI._.mzaomo.
`
`mo.>mzmafi
`
`
`
`mamm__._._.mzao$.:oEz8mama:
`
`Ejofizoo3%:m_._._.Ezmzmo
`
`mamm__._._.mzaoEu
`
`96m__.:>mzm_>En_
`
`.n._s__._.
`
`Page 6 of 25
`Page 6 of 25
`
`
`
`
`
`
`
`
`
`

`
`1
`MEMORY BUS ARBITER FOR A
`COMPUTER SYSTEM HAVING A DSP
`C0-PROCESSOR
`
`BACKGROUND OF THE IN VE\lTION
`
`1. Related Applications
`This application is related to U.S. patent application Ser.
`No. 08t'1S9.139, entided “Dual Bus Concurrent Muttr'-Chan-
`net Direct Memory Access Controller and Method", Ser. No.
`08t'l39.132, entitled “Multiple Register Set Direct Memory
`Access Channel Architecture”. and Scr. No. 08i"l89,I3l,
`entitled "Direct Memory Access Channel Architecture and
`Method for Reception of Network lnfonnntion", each of
`which is assigned to the assignee of the present invention
`and filed concurrently herewith.
`2. Field of the Invention
`
`The present invention relates to digital computer system
`architecture. More particularly, the present invention relates
`to a computer architecture in which multiple processing
`units share a common memory bus and support real-time
`applications.
`3. Description of Related Art
`Until recently. telecommunications and computing were
`considered to be entirely separate disciplines. Telecommu-
`nications was analog and done in real-time whereas com-
`puting was digital and performed at a rate determined by the
`processing speed of a computer. Today, such technologies as
`speech processing, sound processing, electronic facsimile
`and image processing have blurred these lines. In the coming
`years. computing and telecommunications will become
`almost indistinguishable in a race to support a broad range
`of new multimedia (i.e., voice, video and traditional data)
`applications. These applications are made possible by
`emerging digital-processing technologies, which include:
`compressed audio (both high fidelity audio and speed), high
`resolution still images, video. and high speed signal trans-
`mission such as by means of modem or facsimile exchange.
`The emerging technologies will allow for collaboration at a
`distance such as by video conferencing.
`Each of these aspects of real—timc information processing
`may require dedicated processors designed for their imple-
`mentation. However, it is becoming more and more common
`to use programmable digital signal processors (DSP) avail-
`able on the market today. such as the AT&T® DSP32l0.
`DSPs are autonomous processors having their own real—time
`operating systems. As such, they are ideally suited to real-
`time audio and image signal processing.
`In handling rcal—tin1c information such as speech recog-
`nition and modem functionality. a DSP requires a large
`amount of bandwidth to memory for processing the sheer
`volume of data required to effectuate real-time computing.
`FIG. 1 illustrates a typical computer architecture in which a
`CPU 10 is coupled to a memory bus 100. The memory bus
`100 may also be referred to as the system bus or CPU bus.
`In any event, it is this bus which couples the system's CPU
`10 to the U0 interface 15 and the various components of the
`memory subsystem. In FIG. 1, the CPU is in communication
`with a ROM 12 and the main memory subsystem 14 through
`the memory bus 100. The main memory subsystem 14
`usually comprises a memory controller and a large array of
`dynamic random access memory (DRAM) for supporting
`operating applications and data for access by the CPU over
`the memory bus 100. The main memory subsystem is
`distinguished from mass storage 16 which may comprise
`hard magnetic disk drives or a CD-ROM which provide for
`
`Page 7 of 25
`Page 7 of 25
`
`5 ,546,54't'
`
`2
`
`5
`
`I0
`
`20
`
`25
`
`'30
`
`45
`
`50
`
`SS
`
`relatively slow access, high volume storage of information.
`Access times to mass storage are slower in part because of
`the need to process requests through the U0 interface and the
`inherently slower nature of mass storage devices. The
`memory subsystem’s DRAM, on the other hand, is semi-
`conductor mcmory which provides for fairly quick storage
`and retrieval for operating applications and which may be
`fed from the slower mass storage 16 through the U0
`interface 15 over the memory bus 100 to meet the require-
`ments of the CPU 10.
`
`In many computer systems, the U0 interface 15 is also a
`direct memory access (DMA} controller which manages the
`transfer of data between U0 devices and the main memory
`subsystem without requiring the CPU to perform that task.
`The U0 interface 15 may also be used for coupling the
`computer system to other computer systems over a network
`such as an Ethernet local area network.
`
`Also shown coupled to the memory bus 100 in FIG. 1 is
`a digital signal processor (DSP) 20. The logic or controller
`needed to couple the DSP to the memory bus is not shown.
`The DSP 20 may be an off-the-shelf DSP such as the
`AT&T® DSP32l0. Most DSPS include an on-board cache of
`static random access memory (SRAM) which in the case of
`the AT&T DSP3210 is an 8~Kbyte SRAM cache. In prior art
`computer systems, because of the high bandwidth required
`For reai-time processing by a D53 it has not been possible
`for the DSP to run elf of the computer systems DRAM in
`the way the CPU 10 utilizes it without adversely ailecting
`the rest of the computer system. Thus.
`there has been
`provided a large block of SRAM 24 for use by the DSP 20.
`This has allowed the memory bus to be relatively free of
`DSP requests yielding the freedom to process CPU requests
`and requests from IIO devices or networks through the U0
`interface without having to contend for the bandwidth
`required by the DSP 2|].
`A significant disadvantage to the prior art computer
`architecture of FIG. 1 is the requirement of a substantial
`block of static random access memory 24. SRAMS are
`significantly more expensive than DRAM which greatly
`increases the cost of computer systems which incorporate
`SRAM. One object of the emerging multimedia technolo-
`gies is to bring these technologies to the mass market in
`configurations as inexpensive as possible. It is therefore one
`object of the present
`invention to provide a computer
`architecture which incorporates DSP technology for real-
`time data processing without requiring the inclusion of
`expensive SRAM to support the DSP.
`
`SUMMARY OF THE INVENTION
`
`From the foregoing. it can be appreciated that a computer
`architecture which provides for a digital signal processor to
`operate as a co—processor with a CPU over a common
`memory bus without requiring expensive static random
`access memory would be greatly advantageous. Accord-
`ingly, it is an object of the present invention to provide a
`mechanism and method for arbitrating the memory bus
`bandwidth to eificiently allow the use of a digital signal
`processor and a CPU over a common memory bus sharing
`the system’s dynamic random access memory subsystem
`without requiring an expensive block static random access
`memory. It is Further an object of the present invention to
`provide an arbitration scheme in which, in addition to the
`CPU and digital signal processor, a DMA controller and a
`peripheral card expansion bus controller might also access
`the memory bus with all bus masters receiving suificient
`
`

`
`5,546,547
`
`3
`bandwidth over the memory bus to provide for real-time
`isochronous data processing.
`These and other objects of the present invention are
`provided by a computer architecture in which a CPU and
`digital signal processor (DSP) as well as other memory bus
`masters are provided on a common memory bus with the
`system’s dynamic random actress memory subsystem. An
`application specific integrated circuit [ASlC) for arbitrating
`between bus masters is provided which implements an
`arbitration scheme for sharing the bandwidth of the system's
`memory bus to provide the DSP with suificient access to the
`DRAM to carry out real-time, isochronous data processing
`while still allowing the system’s U0 controller to satisfy
`Ethernet communication requirements over the memory bus.
`The arbitration scheme of the present invention is an adap-
`tive arbitration scheme that varies access to the memory bus
`as a function of time and depends upon what operations the
`various bus masters are requesting. The next state of the bus
`arbiter depends on the present state,
`in addition to the
`amount of bus trafile and history of prior requests.
`The arbitration scheme is tuned to maximize accessibility
`of the memory bus to the DSP which has by far the greatest
`bandwidth requirements. A cycle in the arbitration scheme is
`divided into 10 time slices of which 5 slices are available for
`the DSP to assert the memory bus. However,
`the total
`amount of time in a given cycle that the DSP is allotted the
`memory bus is limited by a watchdog timer in the arbitration
`module so as not to choke off the other potential bus masters.
`During the arbitration cycle. each of the potential bus
`masters may signal a bus request over the memory bus and
`a priority scheme defined by a state diagram determines
`which bus master will next have access to the memory bus.
`In the preferred embodiment of the present invention,
`to
`save a pin on the CPU, the CPU does not utilize the means
`for requesting the memory bus. Instead, the default state for
`the arbiter is to assign the memory bus to the CPU when no
`other bus master is requesting it. Further, at the end of each
`arbitration cycle. the last frame is reserved for the CPU
`which may then carry out any desired operation.
`Finally, the present invention is implemented in such a
`way that the clock rate of the DSP need not be synchronized
`with the rest of the modules in the computer system. in this
`way, enhancements in DSP technology will allow faster
`digital signal processors to be incorporated in computer
`systems without requiring total redesign of the architecture.
`The arbiter ASIC effectively has a separate set of state
`machines devoted to the time domain of the digital signal
`processor which operate in conjunction with the state
`machines of the modules operating in the time domain of the
`rest of the computer system. A brief amount of time is
`required for resynchronizing to the diiferent time domains
`on the memory bus which is justified by the increased
`flexibility in the design of the computer architecture.
`
`'25
`
`50
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The objects, features and advantages of the present invcn»
`tion will be apparent from the following detailed description
`in which:
`
`1 illustrates a prior art computer architecture in
`FIG.
`which a digital signal processor requires an expensive static
`random access memory block.
`FIG. 2 illustrates a block diagram of a computer archi-
`tecture incorporating the present
`invention arbitration
`scheme.
`
`4
`FIG. 3 illustrates a state diagram of the arbitration scheme
`for assigning bandwidth slots to the various components of
`the preferred embodiment computer architecture.
`FIG. 4 illustrates a more detailed logical representation of
`the arbiter for implementing the arbitration scheme of the
`present invention.
`FIG. 5 illustrates a tinting diagram showing a simple state
`transition sequence in accordance with a preferred embodi-
`ment implementation of the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`A method and apparatus are described for the arbitration
`of a number of bus masters over a memory bus in a computer
`system architecture supporting a. digital signal processor.
`Throughout this detailed description numerous details are
`specified such as 1.-'0 devices and network standards, in order
`to provide a thorough understanding of the present inven-
`tion. To one skilled in the art, however, it will be understood
`that the present invention may be practiced without such
`specific details. In other instances well—ltnown control stn.tc-
`tures and gate level circuits have not been shown in detail in
`order not to obscure unnecessarily the present invention.
`Particularly.
`the arbitration module for implementing the
`arbitration scheme of the present invention. in the preferred
`embodiment, is implemented in an application specific inte-
`grated circuit (ASIC). With today's manufacturing technol-
`ogy, the development of ASICS generally does not require
`the rendering of fully detailed circuit diagrams. The defini-
`tion of logic functionality and state diagrams allow com-
`puter aided design techniques to design the desired inte-
`grated circuit. Accordingly, the present invention will be
`described primarily in terms of functionality to be imple-
`mented by an ASIC. The software used for developing the
`ASIC chip from the logic defined for the preferred embodi-
`ment will be attached as an appendix. Those of ordinary skill
`in the art, once given the following descriptions of the
`various functions to be carried out by the present invention
`will be able to implement the necessary logic in an ASIC or
`other technology without undue experimentation.
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent disclosure, as it
`appears in the Patent and Trademark Office patent files or
`records, but otherwise reserves all copyrights whatsoever.
`The present invention concerns a computer architecture in
`which a digital signal processor (DSP) operates as a true
`co-processor in the computer system. That is, an arbitration
`technique and mechanism are implemented which allows a
`DSP to reside on the system’ s CPU or memory bus and share
`the memory bus resources with the other potential bus
`masters on the memory bus. The scheme is implemented
`such that the DSP is provided with suflicicnt bandwidth to
`perform real—time digital signal processing using the sys-
`tem’s dynamic random access memory (DRAM) and not
`requiring the incorporation of an expensive block of static
`random access memory (SRAM). DRAM is far less expen-
`sive than SRAM and the elimination of a block of SRAM
`greatly reduces the cost of computer systems. The DSP is
`provided with suificicnt bandwidth on the memory bus to
`perform real-time isochronous signal processing, yet at the
`same time the arbitration scheme of the present invention
`prevents the other bus masters from being starved from the
`bandwidth they require in carrying out their operations.
`
`Page 8 of 25
`Page 8 of 25
`
`

`
`5
`
`6
`
`5,546,547
`
`While the present invention arbitration scheme will be
`described in term of a particular implementation of a com-
`puter system, it should be understood that the broad concept
`of providing for a DSP on a memory bus and sharing the
`system’s DRAM may be extended to other more compli-
`cated systems, or generalized to simpler systems.
`
`Overview of the Present Invention Computer
`System
`
`Referring now to FIG. 2, a preferred embodiment com-
`puter architecture implementing the present invention is
`shown. The constituents of the computer architecture are
`shown coupled to a CPU or memory bus 110. The memory
`bus 110 provides the signal paths for the exchanging of data
`between the various elements on the memory bus. Further
`provided by the memory bus are control lines for such things
`as bus requests and bus granting signals and other system
`level control signals. The signals required for implementing
`the present invention will be described further herein. As
`with the prior art computer systems, the architecture illus-
`trated in FIG. 2 has the CPU 10,
`the ROM 12 and the
`system's main memory subsystem 14 coupled to the
`memory bus 110. It should be understood that in the illus-
`tration the main memory subsystem 14 coupled to the
`memory bus refers to the system’s DRAM and the controller
`required for writing to and reading from the DRAM based
`on a requested transaction. The CPU ll] may be considered
`a potential bus master as contrasted with the memory
`components 12 and 14 which are considered bus slaves. The
`ROM 12 and main memory subsystem 14 will not drive the
`memory bus for transactions on their own behalf.
`The preferred embodiment computer architecture of FIG.
`2 has a number of other potential bus masters coupled to it.
`The U0 interface 30 is used for coupling the memory bus to
`the U0 bus 120 for providing the computer system with a
`number of HO capabilities. The U0 interface 30 of the
`present invention is also a DMA controller which controls
`the transactions between the main memory system 14 and
`U0 devices without requiring the resources of the CPU 10
`for these transactions. The DMA controller of the preferred
`embodiment
`implementation is described in co-pending
`U.S. patent applications: Ser. No. 08!] 89, 139, entitled “Dual
`Bus Concurrent Mufti-Channel Din:-ct Memory Access Con-
`tmllerand Method". Ser. No. 08!] 89,132, entitled “Multiple
`Register Set Direct Memory Access Channel Architecture”,
`and Scr. No. 03l'l89,l3I, entitled “Direct Memory Access
`CltannelArcl1r'lecture and Methodfor Receptiotr cfErliemeI
`Packets assigned to the assignce of the present invention
`and filed concurrently herewith.
`The U0 bus 120 of the preferred embodiment implemen-
`tation as illustrated in FIG. 2 provides the avenue for a
`number of different U0 devices to be incorporated in the
`computer system. For example, the SCSI port 121 is coupled
`through the HO bus 120. SCSI stands for small computer
`system interface which is one of the computer industry's
`standards for coupling U0 devices such as the hard disk
`drive 122 or floppy drives or other storage media and other
`U0 devices to today's microcomputer systems. The com-
`puter system‘s serial port 125 is also coupled to the U0 bus
`120. The serial port can be used for attaching a modem or
`printer or other serial devices. Finally, the U0 bus 120 is
`used to couple the computer system to a local area network
`through the Ethernet port 128. The Ethernet port 128 is used
`for attaching the computer system of the present invention to
`a local area network such as Ethernet or other LAN 129.
`This allows the computer system to communicate with other
`
`25
`
`30
`
`40
`
`45
`
`50
`
`SS
`
`computer systems and share common resources such as
`community printers, etc. As will be described further herein,
`the provision of an Ethernet connection to the present
`invention computer system introduces constraints for the
`bandwidth sharing of the memory bus.
`Another potential bus master coupled to the system bus
`110 of the preferred embodiment computer system is a
`peripheral card expansion bus controller. The peripheral
`card expansion bus controller illustrated in the figure is the
`NuBus controller 40. While the present illustration uses a
`NuBus controller, other peripheral card expansion bus pro-
`tocols are generally known. The NuBus controller 40 is used
`to provide communication between the vatious memory bus
`masters and the system’s expansion bus 130, called NuBus.
`The NuBus provides a fast backplane for coupling such
`things as video controllers 131, RAM expansion cards, mass
`storage device controller cards, or other communications
`devices 132. Again,
`the preferred embodiment computer
`system is constrained by some of the NuBus requirements in
`the bandwidth sharing of the memory bus 110.
`Also, in FIG. 2 there is illustrated another potential bus
`master, the digital signal processor (DSP) 20. Unlike prior
`art computer systems, the present invention provides for the
`D5‘? 20 to reside on the system's memory bus and operate
`from the computer system’s main memory subsystem 14. In
`implementing the present invention this greatly reduces
`system cost by eliminating the need for an expensive block
`of SRAM. In the preferred embodiment implementation, the
`DSP 20 is art AT&T DSP321 0 which provides an internal BK
`SRAM cache. This is an off-the-shelf DSP which is highly
`programmable and has a fairly well defined operating sys-
`tem. The DSP can be programmed to carry out such func-
`tions as speech processing, audio channel control, modern
`emulation, image processing and the like. Many of these
`functions are real-time operations and require a tremendous
`amount of the memory bus bandwidth between the DSP and
`the DRAM of the main memory subsystem 14. For reasons
`that will be described further herein,
`the DSP 20 is not
`constrained to operating at the same clock speed as the rest
`of the components of the computer system. This will require
`some
`resynchronizing for various
`operations
`to be
`described, but provides for flexibility as newer technology
`and faster DSPs are developed.
`Finally, in FIG. 2 there is coupled to the memory bus 110
`the memory controller and arbiter
`(MCA) 200.
`In the
`preferred embodiment implementation, the arbiter 200 is an
`applications specific integrated circuit (ASIC) for arbitrating
`the memory bus 110 between the various bus masters subject
`to the constraints each imposes to provide optimal band-
`width for each, particularly the DSP which is responsible for
`a significant amount of real-time signal processing. In art
`alternative embodiment, the arbiter logic could be designed
`in some other form of logic.
`
`Arbitration Constraints
`
`Because the primary motivation of the present invention
`is to incorporate a digital signal processor as a co-processor
`on a computer system's memory bus while providing it
`suflicient bandwidth to utilize the system's DRAM rather
`than an expensive block of SRAM, it is necessary to talk
`about the various modes of operation of the DSP, particu-
`larly for carrying out real-time processing. As was indicated.
`the DSP 20 is programmable and has an 8-Kbyte intemal
`SRAM cache. Ideally, software written for the DSP should
`be segmented in such a way that blocks may be loaded into
`
`-
`
`Page 9 of 25
`Page 9 of 25
`
`

`
`5,546,547
`
`'7
`the cache of the DSP allowing the DSP to not as much of the
`time as possible from its internal cache. Thus. one mode in
`which the DSP will utilize the memory bus 110 is to read a
`large block memory from the DRAM 14 into its internal
`SRAM. This first mode of operation on the memory bus can
`be referred to as a “block read". Another mode of operation
`concerns the handling of data that has already been pro-
`cessed by the DSP. In many cases it will be necessary to push
`that data back out to the DRAM so that some other parts of
`the computer system can utilize it. Thus. the capability of
`bursting data out is a second mode of operation which may
`be referred to further herein as a “block write".
`
`Because of the nature of some software, it is not always
`guaranteed that the code is going to be divisible into discrete
`blocks for block read operations. There may be times when
`it is necessary to repeatedly access the DRAM, effectively
`supporting a scheme where the DSP executes code directly
`from the DRAM. As contrasted with a block read, this might
`be considered a situation of “back-to-back single reads“
`from the DRAM. The occurrence of these back-to—back
`operations is recognizable and will be considered by the
`arbiter scheduling algorithm to be described further herein.
`Finally, during the course of normal operation there may be
`situations in which the DSP requires only a single piece of
`data from the DRAM. These types of read operation are
`referred to as “scattered-single reads". Because the DSP will
`be processing many real—time operations as well as others,
`each of these modes of operation where the DSP must have
`access to the memory bus must be taken into consideration
`by the arbitration scheme of the present invention.
`In addition to the DSP’s huge requirement for bandwidth
`on the memory bus, the arbiter 200 must also contend with
`constraints imposed by other resources on the memory bus.
`Particularly, the HO interface 30 provides the interconnec-
`tion of the computer system to an Ethernet
`local area
`network. This Ethernet connection should never be choked
`ell" because losing an Ethernet packet results in a tremendous
`penalty in time for recovery. Thus, the HO interface 30 must
`be guaranteed at least a predetermined amount of time for
`every arbitration cycle to support
`the system's Ethernet
`connection. The floppy disk drive, serial ports and audio
`inputfoutput DMA, in a similar fashion, also require some
`guaranteed memory bus bandwidth. Likewise, with all other
`constraints taken into account, the system’s SCSI perfor-
`mance should not be allowed to degrade below an accept-
`able level.
`
`Similar to the U0 interface constraints, there are con-
`straints imposcd by the computer system being coupled to an
`expansion bus through the NuBus controller 40. Like the U0
`interface, there are certain latencies that NuBus introduces
`which must be provided for thus requiring a guaranteed
`amount of memory bus availability each arbitration cycle for
`the NuBus controller. Finally, though the CPU does very
`little in the way of real-time operation in a system having a
`DSP, it still must have some access every arbitration cycle
`to the main memory subsystem 14.
`
`I0
`
`20
`
`35
`
`45
`
`50
`
`55
`
`Arbitration Algorithm
`
`in a
`it can be appreciated that
`From the foregoing,
`computer system in which a DSP resides on the memory bus
`and satisfying all the potential memory bus master’s band-
`width requircmertts will have to be finely tuned. During the
`operation of the computer system of the present invention,
`the four potential bus masters, the CPU, the DSP, the U0
`interface and the NuBus controller may each at various
`
`8
`the
`times require the memory bus. When this occurs,
`resource propagates a bus request signal over the memory
`bus 110 to the arbiter 200. A figure referred to further herein
`will indicate more clearly what signals are required for the
`va.rious bus requests. When the memory bus is available for
`assignment, the arbiter 200 will issue a bus grant signal to
`one of the resources according to a priority scheme which
`takes into consideration all of the constraints described
`above as well as various previous states of the system and
`the present state of the system.
`Refen-ing now to FIG. 3, a state diagram is illustrated
`which is used to derive the logic of the arbiter ASIC 200.
`This state diagram is the preferred embodiment arbitration
`scheme for the implemented computer system described
`with respect to FIG. 2 which has, in addition to a CPU and
`a DSP on the memory bus, an U0 interface for coupling the
`system to a local area network and other U0 devices as well
`as a NuBus interface with each imposing considerable
`constraints. The state diagram illustrated in FIG. 3 is instru-
`mental in developing the VERILOG code or equivalent in
`the production of the arbiter ASIC 200. The code for the
`preferred embodiment arbitration scheme is set forth in
`Appendix A.
`The bus arbiter 200 follows the priority scheme illustrated
`by the state diagram of FIG. 3. The arbiter receives the bus
`request signals from the potential bus masters, and based on
`the present state and a specified priority order asserts an
`appropriate bus grant signal. In the preferred embodiment
`implementation. to save a pin on the CPU, the CPU 10 does
`not issue bus request signals.
`Instead,
`the state of the
`memory bus assignment defaults to the CPU and remains
`parked on the CPU until other resources request the memory
`bus. The CPU is also provided with one time slot in the
`priority scheme to be described in which it is granted the
`memory bus.
`'
`Each circle in the arbiter state diagram of FIG. 3 repre-
`sents a present state memory bus assignment and the arrows
`represent the state transition from a current bus master to the
`next bus master when the specified conditions are met.
`Because the DSP has the largest bus bandwidth requirement,
`the system is optimized to meet its need and support its
`real-time operations. In order to optimize this requirement
`and still give a reasonable bandwidth to the other bus
`masters, the DSP is assigned 5 time slots among a total of 10
`in the arbitration loop. The arbitration loop starts at DSP_1
`state 301 and ends at the CPU state 310. The CPU state 310
`is the point of reference which also designates the comple-
`tion of the entire arbitration loop. The NuBus controller 40
`and the U0 interface 30 each own 2 time slots in the
`arbitration loop while the CPU 10 owns only 1 slot. The
`sequence through the arbitration loop is the following:
`DSP,1-—9NuB_1—>DSP_2—>lOB_1—>DSP_3—-> NuB_
`2—>DSP,_4—>IOB___2—>DSP_5—>CPU. This will be the
`order of memory bus ownership if all bus masters are
`requesting the bus in every state, though with some restric-
`tions to be described further herein.
`
`The state diagram of FIG. 3 illustrates that from a state
`after reset at the CPU memory bus state a transition to the
`DSP_1 state 301 is made if the DSP is requesting the
`memory bus and a special flag has not been asserted. The
`special flag concerns a degenerate state with respect to the
`NuBus controller which will be described further herein.
`From the DSP___1 state 301 the arbiter will next assign the
`state of the memory bus to the Nt1Bus controller state 302 if
`the NuBus controller is requesting the memory bus. If the
`NuBus controller is not requesting the memory bus when the
`system is in DSP_I state, but the DSP continues to request
`
`Page 10 of 25
`Page 10 of 25
`
`

`
`5,546,547
`
`9
`it. the memory bus will remain assigned to the DSP and
`transfer to the DSP__2 state 303. Similarly, if neither the
`NuBus controller nor the DSP is requesting the memory bus
`while the system is in DSP state 301, and the HO interface
`does request the bus, the arbiter will assign the memory bus
`to the IOB_I state 304. From the DSP_1 state 301, if no
`otltcr resource is requesting the memory bus when the slot
`is c