Ulllted States Patent
`
`[19]
`
`Bowes et at.
`
`||||I|llllllllIll||||||||||||||||||||||l||lllll|||lll|||||||||l||ll|l||llll
`U8005546547A
`
`[11] Patent Number:
`
`[45] Date of Patent:
`
`5,546,547
`
`Aug. 13, 1996
`
`[54]
`
`MEMORY BUS ARBITER FOR A
`COMPUTER SYSTEM 1.11;va A nsp
`
`5,313,591
`5353,41?
`
`5:15:94 Averill
`10t1994 Fuoco et a].
`
`
`
`3951325
`3951325
`
`[75]
`
`[73]
`
`{21]
`
`[22]
`
`[51]
`[52}
`[53]
`
`[56]
`
`CO'PROCESSOR
`_
`‘
`_
`_
`_
`mamm- MICWI J- 30m, Cupmmév Fwd 19-
`Yazdy, Belmont, both of Caltf.
`
`Primary Examiner—Jack B. Harvey
`Assistant Examiner—David A. Wiley
`Atromey, Agent, or Fim—Biakely, Sokolofi", Taylor a. Zar-
`man
`
`Assignec: Apple Computer, Inc., Cupcrtino,
`Calif.
`
`’ 1994
`
`AWL N05 “39’1”
`F‘lcd:
`_
`1
`Jan 28
`G961? 13:00
`Int. Cl.6
`............................................. 3951'294; 395t293
`US. Cl.
`Field of Search ...................................... 395825, 425
`
`References Cited
`
`4,641,238
`4,923,234
`4.937.529
`5,263,163
`5,301,232
`
`U'S' PATENT DOCUMENTS
`2:193? Kncib ...................................... 395525
`
`.. 393425
`511990 Kitamura ct a1.
`.. 395825
`111991 Craft ct al.
`
`.. 395825
`1111993 Holt et a].
`
`4:15:94 Aminl cl a1. ............................ 3951325
`
`ABSTRACT
`[57]
`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 memory. An arbitration cycle is divided into
`10 slices of which 5 slices are provided in 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 system’s CPU- A
`default state when no memoryr bus resource is requesting the
`system memory bus parks the memory bus on the CPU. The
`arbitration scheme provides sufficient bandwidth for real-
`time signal processing by the digital signal processor oper-
`ating from the System‘5 dynamic random access memory
`while also providing Sufficient bandwidth for a local area
`network interface through the system’s L’O interface.
`
`3 Claims, 5 Drawing Sheets
`
`129
`
`LAN
`
`ET423
`
`E‘s—c
`LLIC)P
`ETH
`
`SERIAL PORT
`SCSI PORT
`
`a:
`.2i...
`Cl
`
`2D Et
`
`oI
`
`422
`
`x.
`
`125
`
`14
`W
`MAIN MEMORY
`
`10
`
`200
`
`12
`
`SUBSYSTEM
`um (DRAM)
`
`MEMORY BUS
`
`~110
`
` m
`
`CONTROLLER_—
`
`3D~
`
`NUBUS
`corneouen
`
`~40
`
`420
`
`co
`2')
`on
`
`Q
`
`NUBUS
`
`430
`
`12L-
`
`131~
`
`COMMUNICATIONS ~132
`
`Page 1 of 25
`Page 1 of 25
`
`HTC-LG-SAMSUNG EXHIBIT 1003
`HTC-LG-SAMSUNG EXHIBIT 1003
`
`

`

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

`

`US. Patent
`
`Aug. 13, 1996
`
`Sheet 2 of 5
`
`5,546,547
`
`14
`
`10
`
`200
`
`12
`
`MNNMEMOHY
`SUBS
`
`m IDIEIII
`
`a
`‘—
`
`Z
`S
`
`a
`7
`‘—
`LL!
`2..
`- 55g-In.
`
`3E ID
`EEO
`N
`$3-
`F
`
`30$ PORT
`
`121~
`
`a
`7
`.x
`.9
`£3
`E(U
`
`m
`.2I—
`C]
`
`I
`
`I
`
`MEMORY BUS
`
`~110
`
`I
`
`
`NUBUS
`CONTROLLER
`
`40
`
`a
`T
`
`‘3
`ED
`O
`2
`
`NUBUS
`
`~130
`
`131~ VIDEO
`
`COMMUNICATIONS 432
`
`Figure 2
`
`Page 3 of 25
`Page 3 of 25
`
`

`

`US. Patent
`
`Aug. 13, 1996
`
`Sheet 3 of 5
`
`5,546,547
`
`m.Exam
`
`wam?
`
`
`me?aa?a52
`
`9.2:w32:
`
`Page 4 of 25
`Page 4 of 25
`
`

`

`US. Patent
`
`Aug. 13, 1996
`
`Sheet 4 of 5
`
`5,546,547
`
` INTERFACE UNIT
`
`DSP
`STATE
`MACHINE
`
`INTE FIFACE UNIT
`
`NON-USP
`STATE
`
`NON-USP
`MACHINES
`
`BUS INTERFACE
`UNIT
`
`
`
`
`
`
`
`
`
`DSF
`241~
`
` CPU LOCK
`WATCHDOG
`TIMER
`
`
`BUS ARBITRATION UNIT
`LOGIC
`
`Figure 4
`
`Page 5 of 25
`Page 5 of 25
`
`

`

`US. Patent
`
`Aug. 13, 1996
`
`Sheet 5 of 5
`
`5,546,547
`
`m.333%
`
`mamwI._.ngoDuo
`
`:10ME.>mzm>ED
`
`mmEmmqmxb>mzuZmD
`
`
`
`:ngomamm=.Fm.”awn.zmIB
`
`
`
`22mg.mammI._.mzfisoawn
`mmEmmEm3...>m2m>EDmamm5,ngoawn
`
`mamwI._.ngomo—
`
`mo.>mzmamo
`
`
`
`mamm=.:.ngomwfiOmHzoomama:
`
`mDmm1...wzgo2.5
`
`
`
`:mjoEzOomama:ME.>mZuzmoDuoMT;>mzm>_mn_
`
`m2_._.
`
`
`
`DuoFqumamoFImezz_.mmo:mo
`
`Page 6 of 25
`Page 6 of 25
`
`
`
`
`
`
`

`

`1
`MEMORY BUS ARBITER FOR A
`COMPUTER SYSTEM HAVING A DSP
`CO-PROCESSOR
`
`BACKGROUND OF THE INVENTION
`
`1. Related Applications
`This application is related to U.S. patent application Ser.
`No. 08l189.139, entitled “Dual Bus Concurrent Mufti-Chan-
`nei Direct Memory Access Controller and Method", Scr. No.
`08i139.132, entitled “Multiple Register Set Direct Memory
`Access Channel Architecture”. and Scr. No. 081181131,
`entitled “Direct Memory Access Channel Architecture and
`Method for Reception of Network Infonnotion", 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 Shaft: 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. 'Iblecommu-
`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:
`comprched audio (both high fidelity audio and speed}, high
`resolution still images, video. and high speed signal trans-
`missiou 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—time 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® DSP3210.
`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 real—time 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 efiectuaw 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,547
`
`2
`
`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 memory which providcs for fairly quick storage
`and retrieval for operating applications and which may be
`fed from the slower mass storage 16 through the HO
`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 olf-the-shelf DSP such as the
`AT&T® DSP3210. 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 real-time processing by a DSP, it has not been possible
`for the DSP to ma oil” of the computer system’s DRAM in
`the way the CPU 10 utilizes it without. adversely afiecting
`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 L'O devices or networks through the HO
`interface without having to contend for the bandwidth
`required by the DSP 20.
`A significant disadvantage to the prior art computer
`architecture of FIG. 1 is the requirean 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 sufficient
`
`5
`
`10
`
`15
`
`20
`
`25
`
`'30
`
`35
`
`45
`
`50
`
`55
`
`6t]
`
`65
`
`

`

`5,546,547
`
`3
`bandwidth over the memory bus to provide for real-time
`isoehronous 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 access memory subsystem. An
`application specific integrated circuit (ASIC) 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 suificicnt moms to the
`DRAM to carry out real-time, isoehronous data processing
`while still allowing the system’s UO 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 traffic 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 difierent time domains
`0n the memory bus which is justified by the increased
`flexibility in the design of the computer architecture.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The objects, features and advantages of the present invenn
`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.
`
`10
`
`15
`
`'25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`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 embodiv
`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 DO 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—known control struc-
`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 ASle 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 foilowing 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’ 5 CPU or memory has 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 sufficient 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 sufficient bandwidth on the memory bus to
`perform real-time isoehronous 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 1|] 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 has 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 eo-pending
`US. patent applications: Ser. No. 08l189,l39, entitled “Dual
`Bus Concurrent Main-Channel Direct Memory Access Con~
`tmllerund Method". Ser. No. 08!] 89.132, entitled “Multiple
`Register Set Direct Memory Access Channel Architecture”,
`and Ser. No. 03l189,l3l, entitled “Direct Memory Access
`Channel Architecture and Methodfor Reception ofErhemer
`Packets“, assigned to the assignee 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
`
`10
`
`15
`
`25
`
`30
`
`35
`
`4o
`
`45
`
`50
`
`SS
`
`65
`
`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 has controller. The peripheral
`card expansion bus controller illustrated in the figure is the
`NuBus controller 49. 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 various memory bus
`masters and the system’s expansion bus 130, called NuBus.
`The NuBus provides a fast backplanc 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 en 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 an AT&T DSP3210 which provides an internal BK
`SRAM cache. This is an oif-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 funcfi
`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 an
`alternative embodiment, the arbiter logic could be designed
`in some oLhcr 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 internal
`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 min 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 “scatterednsingle 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
`oil" 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
`inputr‘output 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 HO interface constraints, there are con-
`straints imposed 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.
`
`10
`
`[5
`
`20
`
`25
`
`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 requirements 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
`various 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.
`Referring 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 ] slot. The
`sequence through the arbitration loop is the following:
`DSP_,1ANuB_1—>DSP_2—>IOB_l—>DSP_3—-+ NuB_
`Z—tDSPH4—>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, thorrgh wilh 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 NuBus 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 has
`while the system is in DSP state 301, and the U0