United States Patent [19J
`Carmichael et al.
`
`[54] METHOD AND APPARATUS FOR
`CONTROLLING 1/0 CHANNELS
`RESPONSIVE TO AN AVAILABILITY OF A
`PLURALITY OF 1/0 DEVICES TO
`TRANSFER DATA
`
`(75]
`
`Inventors: Richard D. Carmichael. Longmont;
`Joel M. Ward; Michael A. Wmchell.
`both of Fort Collins. all of Colo.
`
`(73] Assignee: LSI Logic Corporation. Milpitas,
`Calif.
`
`c211 Appl. No.: osno2,998
`
`[22] Filed:
`
`Aug. 26, 1996
`
`Related U.S. Application Data
`
`[63] Continuation of application No. 08/407,439, Mar. 17, 1995,
`abandoned.
`Int. Cl.6
`...................................................... G06F 13/00
`[51]
`[52] U.S. Cl ............................ 395/845; 395/827; 395/840
`[58] Field of Search ..................................... 395/825, 826,
`395/827. 840. 841. 844. 845, 800. 600
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,371,932
`4,782,439
`4,805,137
`4,807,121
`4,821,170
`4,831,523
`5,016,160
`5,031,097
`5,131,081
`5,179,709
`5,185,876
`5,206,933
`5,212,795
`5,251,303
`5,251,312
`5,301,279
`5,305,319
`
`2/1983 Dinwiddie, Jr. et al. ............... 3641200
`1111988 Borkar et al. ........................... 3951800
`2/1989 Grant et al .............................. 3641900
`2/1989 Halford ................................... 3641200
`4/1989 Bernick et al .......................... 3951856
`5/1989 Lewis et al ............................. 3641200
`5/1991 Lambeth et al ......................... 3951844
`7/1991 Katakami et al ....................... 3951848
`7/1992 MacKenna et al ..................... 3951275
`111993 Bailey et al ............................ 395n25
`2/1993 Nguyen et al. ......................... 395/425
`4/1993 Farrell et al. ........................... 395/200
`5/1993 Hendry .................................... 395n25
`10/1993 Fogg, Jr. et al ........................ 395/275
`10/1993 Sodos ...................................... 395/425
`411994 Riley et al .............................. 395/275
`4/1994 Sowell ................................. 370/85.13
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll lllll lllll lllll llllll Ill lllll llll
`US005894560A
`5,894,560
`[HJ Patent Number:
`[45J Date of Patent:
`Apr. 13, 1999
`
`5,355,476 10/1994 Fukumura ............................... 395/600
`5,367,639 1111994 Sodos ...................................... 3951275
`1/1995 Sodos ...................................... 3951425
`5,386,532
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`
`0317481
`0530543
`0537401
`0549924
`9306553
`
`5/1989 European Pat. Off ......... G06F 15/16
`3/1993 European Pat. Off ......... G06F 13132
`411993 European Pat. Off ......... G06F 15/16
`7/1993 European Pat. Off ......... G06F 13/28
`4/1993 WIPO ............................. G06F 13/28
`
`OTHER PUBLICATIONS
`
`IBM Technical Disclosure Bulletin. Jan .• 1994; DMA Con(cid:173)
`troller Channel Interlocking; vol. 37. No. 1; pp. 337-342.
`IBM Technical Disclosure Bulletin, Feb.. 1995; Priority
`Scheme for Arithemetic Logic Unit and Dataflow Usage by
`P1394 Isochronous Hardware; vol. 38. No. 2; pp. 477-480.
`Programming Interface for Bus Master IDE Controller Revi(cid:173)
`sion 0.9; Jun. 14, 1994; Brad Hosler; Intel Corporation; pp.
`1-6.
`
`Primary EXaminer-Christopher B. Shin
`Attome); Agent, or Firm-David K. Lucente
`
`[57]
`
`ABSTRACT
`
`An apparatus and method for improving the input/output
`performance of a computer system under the control of a
`multi-tasking. multi-threaded operating system. In
`particular, the invention provides an apparatus and method
`to chain contiguous DMA scatter gather sub blocks of a PRD
`table for channel 0 with contiguous DMA scatter gather sub
`blocks of a PRD table for channel 1. using a single data
`manager, while maintaining maximum media bandwidth.
`DMA block transfers are scheduled based on the availability
`of data from the 1/0 device's buffer memory, thus minimiz(cid:173)
`ing both media or network idle time as well as minimizing
`1/0 bus idle time. Near maximum aggregate bandwidth of
`multiple 1/0 buses and their associated devices is obtained
`The apparatus and method thus provides significant perfor(cid:173)
`mance advantages over prior techniques having two 1/0
`channel systems implemented with a single data manager.
`
`7 Claims, 15 Drawing Sheets
`
`200
`
`1/0 cH1iNtt 0 0 0
`
`ITJ
`
`1/0 CHANN[l. I
`
`IT]
`QJ 0
`
`ITJ 0
`
`202
`
`SINGLE CHANNEL OPERATION
`
`ITJ
`1/0 C~NEL D 0 0
`ITJ
`ITJ 0
`[_(J 0
`
`1/0 CHANNEL 1
`
`204 -
`
`CONCURRENT CHANNEL OPERATION
`
`PRO T ABU rNTRIES
`
`'
`
`1/0 CHANNF-1 I
`
`PREEMPT
`PRO
`CHANNEL 0
`
`1/0 CHANNEL U 0 0
`[J] Q]
`ITJ QJ m 0
`
`PRO 0 0
`
`RfSJOHl
`
`CHANNEL 0
`
`0
`
`CONCURRENT CHANNEL OPlilATION WITH PllEEMPTION CHANNEL o
`ITJ
`1/0 Cl°:ANNEI 0 0 0
`ITJ
`110 CHANNll 1 CD PR~PT ~ RE~~gRE 0 m 0
`
`206
`
`CHANfJEL I
`CHl\NNEL 1
`CONGlnlRFNT CHAJ\INEL OPERATION WITH PREEMPTION CHANNfl I
`
`IJO
`CHANNEL 0
`
`1/0
`CHANN[l. I
`
`A
`B
`c
`0
`
`E
`F
`G
`H
`
`1/0 DEVICE 0
`
`1/0 OlVICf 2
`
`-
`
`~ ~-
`
`M
`
`I
`j
`
`1/0 DEVICE 1
`
`1/0 DEVICE 3
`
`Ex.1053.001
`
`DELL
`
`

`

`5,894,560
`Page 2
`
`U.S. PPJENT DOCUMENTS
`
`5,388,219
`5,388,237
`5,404,454
`5,418,909
`5,438,665
`
`2/1995 Chan et al ....•••.•••..................• 3951275
`211995 Sodos ...................................... 395/425
`4/1995 Parks ....................................... 3951275
`5/1995 Jackowski et al ..•..............•.... 3951275
`8/1995 Taniai et al. ............................ 395/845
`
`5,551,006
`5,574,944
`5,613,162
`5,655,151
`5,671,439
`5,687,39'2
`5,701,516
`5,740,466
`
`811996 Kulkarni ................................. 71l/146
`11/1996 Stager ..................................... 395/825
`3/1997 Kabenjian ............................... 395/842
`811997 Bowes et al ............................ 395/842
`9/1997 Klein et al .............................. 395/821
`1111997 Radko ..................................... 395/842
`1211997 Cheng et al ............................ 395/842
`411998 Goldman et al ........................ 395/825
`
`Ex.1053.002
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 13, 1999
`
`Sheet 1of15
`
`5,894,560
`
`FIG. 1
`
`CPU
`
`I
`
`PROCESSOR
`BUS
`
`I 34
`
`-
`
`BRIDGE
`
`- -.
`
`'---36
`
`21
`
`20
`\
`
`28
`
`..
`
`r-+
`
`PROCESSOR
`INTERFACE
`
`14-
`
`10 CONTROL DEVICE 22
`
`-
`
`/
`
`PRD TABLE ENTRY
`BASE ADDRESS (31 :2)
`(DESCRIPTOR TABLE
`POINTER REGISTER\
`
`...
`
`(- 24
`
`OMA ENGINE AND
`1--+ CONTROL LOGIC AND 14-
`ADDRESS I DATA
`BUFFER
`
`'--+
`
`1/0 INTERFACE
`LOGIC
`
`1.-
`, __
`
`26
`
`~
`
`-32
`
`1/0 INTERFACE BUS
`(TO 1/0 DEVICE)
`
`PHYSICAL REGION DESCRIPTOR TABLE
`MEMORY REGION PHYSICAL
`ADDRESSES (31 : 1)
`
`I RESERVED I BYTE COUNT
`
`(15:1)
`MEMORY REGION PHYSICAL
`ADDRESSES ( 31 : 1 )
`
`I RESERVED I BYTE COUNT
`
`.. ~·-- '--3 7
`
`.... ·-
`
`.... •---
`
`-~'.
`
`38
`
`(15:1)
`"8 BYTE PHYSICAL
`REGION
`DESCRIPTOR
`
`•
`:
`
`I TABLE ENTRIES
`l BYTE COUNT
`
`MEMORY REGION PHYSICAL
`ADDRESSES (31 : 1)
`·I
`END OF
`TRANSFER BIT RESERVED
`
`<15:1)
`
`-.i._
`
`)
`(
`38
`I+-
`
`OMA DATA (31:0)
`
`OMA DATA (31 :0)
`
`. . .
`
`OMA DATA (31 :0)
`
`\_ 40-~
`
`·,
`
`OMA DATA (31 :0)
`
`OMA DATA (31 :0)
`
`.
`. .
`
`OMA DATA (31 :0)
`
`MAIN MEMORY
`
`OMA DAT A (31 :0)
`
`OMA DATA (31 :0)
`. .
`.
`OMA DATA (31 :O)
`
`I
`
`I
`
`I
`
`I
`
`I
`
`\ __ 40
`
`--- 40
`
`/ /
`
`30
`'
`
`I
`
`Ex.1053.003
`
`DELL
`
`

`

`

`

`

`

`U.S. Patent
`
`Apr. 13, 1999
`
`Sheet 4of15
`
`5,894,560
`
`FIG. 4
`
`CPU
`
`J
`
`PROCESSOR
`BUS
`
`\.
`34
`
`36
`I.
`\
`
`-
`
`BRIDGE
`
`... - 21
`
`120
`\
`I
`
`28 I
`,.....
`
`PROCESSOR
`INTERFACE
`
`~
`
`/
`
`PHYSICAL REGION DESCRIPTOR TABLES
`CHANNEL O I 8 BYTE PRO TABLE ENTRIES:
`DESCRIPTOR I 8 BYTE PAD TABLE ENTRIES~
`.
`. .
`TABLE
`ENTRIES
`I 8 BYTE PRD TABLE ENTRIES}
`
`-·
`
`/ 137
`
`/
`
`,-139
`
`CHANNEL 1 I 8 BYTE PRD TABLE ENTRIES:
`.
`DESCRIPTOR 18 BYTE PRO TABLE ENTRIES}
`. .
`TABLE
`ENTRIES
`18 BYTE PRO TABLE ENTRIES~
`I DMA DATA f31 :O}
`I
`I
`I
`I DMA DATA ?1 :O~
`I
`
`DMADATA 31:0
`
`OMA DATA (31:0)
`
`OMA DATA 31:0
`
`OMA DATA (31 :O)
`
`MAIN MEMORY
`
`I
`I
`
`.
`. .
`
`140--)
`
`I• -
`
`• -
`
`-
`
`'1
`i
`140
`
`10 CONTROL DEVICE 121
`'
`\
`i
`
`PRO TABLE ENTRY
`BASE ADDRESS (31 :2}
`
`(DESCRIPTOR TABLE -
`-- (DESCRIPTOR TABLE -
`
`!--.
`
`POINTER REGISTER)
`CHANNEL 0
`PRO TABLE ENTRY
`BASE ADDRESS (31 :2)
`
`POINTER REGISTER)
`CHANNEL 1
`
`123
`
`\
`.
`
`-124
`I
`OMA ENGINE AND
`!--. CONTROL LOGIC AND
`ADDRESS/ DATA
`BUFFER
`
`.--
`
`--
`
`l/OINTERFACE
`LOGIC
`
`i -
`
`-'1
`
`• 126
`
`·~
`127
`"
`IDEINTERFACE
`BUS O
`
`+ -
`-129
`IOEINTERFACE
`BUS 1
`
`OMA DATA 31:0
`
`OMA DATA (31:0)
`
`DMA DATA 31 :O
`
`OMA DATA {31 :0)
`
`I DMA DATA {31 :O~
`I
`I DMA DATA ~31 :Oi
`I
`I OMA DATA ~31 :O~
`I
`
`OMA DATA 31 :O
`
`OMA DATA (31 :0)
`
`140 )
`
`DMADATA 31:0
`
`I OMA DATA f 31 :Oi
`I
`
`OMA DATA (31 :O)
`
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`. .
`.
`
`140
`
`140
`
`-
`
`.
`
`.
`
`\ 140
`
`130
`
`Ex.1053.006
`
`DELL
`
`

`

`

`

`

`

`

`

`

`

`

`

`--------1-TIME
`
`1/0
`CHANNEL 0
`BUS
`OPERATION
`
`TRANSFER
`PRO TABLE
`ENTRY 1
`
`TRANSFER
`PRO TABLE
`ENTRY 2
`
`TRANSFER
`FINAL PRO
`TABLE
`ENTRY
`
`EXPECTING
`COMPLETION
`INTERRUPT
`CHANNEL 0
`
`TRANSFER
`NEW PRO
`TABLE
`ENTRY 1
`
`TRANSFER
`NEW PRO
`TABLE
`ENTRY 2
`
`1/0
`CHANNEL 1
`BUS
`OPERATION
`
`TRANSFER
`PRO TABLE
`ENTRY 1
`
`TRANSFER
`PRO TABLE
`ENTRY 2
`
`HOLDING
`OFF FINAL
`PRO TABLE
`ENTRY
`
`CH 0 IRQ
`EXPECTING
`SERVICED
`COMPLETION
`TRANSFER
`INTERRUPT
`FINAL CHI PRD
`TABLE ENTRY CHANNEL 0
`
`PROCESSOR
`INTERRUPT
`OPERATION ---------------------.1
`
`FIG. 6C
`
`~
`00
`•
`~ =
`("'O =
`
`'""""
`'""""
`
`~ :'I -~ -~
`~ a -Q
`s, -°'
`
`~
`
`Ol
`QO
`'-= ~
`Ol
`~ =
`
`~
`
`Ex.1053.012
`
`DELL
`
`

`

`

`

`

`

`200
`
`'
`1/0 CHANNEL 0 0
`
`1/0 CHANNEL 1
`
`[I] IT] 0
`
`202-
`
`SINGLE CHANNEL OPERATION
`
`FIG. 9
`
`[TI 0
`
`ITJ 0
`
`1/0
`CHANNEL O
`
`~
`
`~
`
`1/0
`CHANNEL 1
`
`..,,
`
`PRO TABLE ENTRIES
`
`A
`B
`c
`D
`
`E
`F
`G
`H
`
`1/0 DEVICE 0
`
`1/0 DEVICE 2
`
`'
`[I] ITJ 0
`1/0 CHANNEL 0 0
`[TI 0
`[§] 0
`
`1/0 CHANNEL 1
`
`CONCURRENT CHANNEL OPERATION
`
`204--,
`\
`
`1/0 CHANNEL 1
`
`vo CHANNEL o 0 0
`IT] 0
`
`PREEMPT
`PRD
`CHANNEL 0
`
`BIT~ m PRO 0 0
`[§] 0
`
`RESTORE
`
`CHANNEL 0
`
`206-·,,
`,
`
`CONCURRENT CHANNEL OPERATION WITH PREEMPTION CHANNEL 0
`
`[I] ITJ
`1/0 C~NNEL 0 0
`[I]
`f71 PREEMPT ~ RESTORE ~
`L£.J
`1/0 CHANNEL 1 ~ PRO ~ PRO
`CHANNEL 1
`CHANNEL 1
`CONCURRENT CHANNEL OPERATION WITH PREEMPTION CHANNEL 1
`
`[I] 0
`
`~
`
`==
`
`I
`J
`
`M
`
`1/0 DEVICE 1
`
`1/0 DEVICE 3
`
`~
`
`0
`00 •
`~
`"""" ~ a
`
`> "'O
`~ .....
`~ .....
`~
`
`r'1 =(cid:173)~ ::a.
`..... w
`s,
`.....
`f.l'I
`
`Ol
`~ 00
`'e. ~
`~ =
`
`Ol
`
`Ex.1053.015
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 13, 1999
`
`Sheet 14 of 15
`
`5,894,560
`
`FIG. 10
`
`PCIBUS
`'~
`
`~-'-121
`
`128
`' \
`
`I
`
`I
`
`PCIBUSINTERFACE
`
`1/0 CONTROL DEVICE
`
`121
`~ - _,
`(
`PAD TABLE ENTRY BASE ADDRESS (31 :2)
`(DESCRIPTOR TABLE POINTER REGISTER)
`CHANNEL 0
`PRO TABLE ENTRY BASE ADDRESS (31 :2)
`(DESCRIPTOR TABLE POINTER REGISTER)
`CHANNEL 1
`
`120
`
`I-
`
`~
`
`-
`
`-I
`
`--
`
`-
`
`-
`
`t
`
`L123
`
`OMA ENGINE AND CONTROL LOGIC
`ANO ADDRESS/DAT A BUFFER
`
`-
`
`L-124
`
`1/0 INTERFACE LOGIC
`
`--
`
`Jo
`
`,
`
`CHANNELO
`IDE BUS
`
`..
`'-- 126
`
`•
`..
`CHANNEL 1
`IDE BUS
`
`Ex.1053.016
`
`DELL
`
`

`

`U.S. Patent
`
`Apr. 13, 1999
`
`Sheet 15 of 15
`
`5,894,560
`
`FIG. 11
`
`PCIBUS
`"
`-"-- 121
`
`128
`
`<.__
`
`)
`
`~ PCIBUSINTERFACE
`
`1/0 CONTROL DEVICE
`
`_____.
`
`_____.
`
`PRO TABLE ENTRY BASE ADDRESS (31:2)
`(DESCRIPTOR TABLE POINTER REGISTER)
`CHANNEL 0
`PRO TABLE ENTRY BASE ADDRESS (31 :2)
`(DESCRIPTOR TABLE POINTER REGISTER)
`CHANNEL 1
`PRO TABLE ENTRY BASE ADDRESS (31 :2)
`r---+ (DESCRIPTOR TABLE POINTER REGISTER)
`CHANNEL 2
`
`l c224
`
`" 120
`
`I
`
`121
`i
`
`/
`
`I+--
`123
`j
`
`-
`
`l_ 125
`
`r--+-
`
`_____.
`
`OMA ENGINE AND CONTROL LOGIC
`AND ADDRESS/DAT A BUFFER
`
`~
`
`OMA ENGINE AND CONTROL LOGIC
`AND ADDRESS/DAT A BUFFER
`"
`'
`
`~
`
`r
`
`..
`
`\ - 225
`
`-
`
`---
`
`I
`
`--226
`
`--+
`
`1/0 INTERFACE LOGIC
`
`'
`
`~
`
`r
`
`CHANNEL 0
`IDE BUS
`
`CHANNEL 1
`IDE BUS
`
`CHANNEL 2
`ETHERNET
`
`Ex.1053.017
`
`DELL
`
`

`

`5.894.560
`
`1
`METHOD AND APPARATUS FOR
`CONTROLLING 1/0 CHANNELS
`RESPONSIVE TO AN AVAILABILITY OF A
`PLURALITY OF 1/0 DEVICES TO
`TRANSFER DATA
`
`This is a continuation of application Ser. No. 08/407.439
`filed Mar. 17. 1995 now abandoned.
`
`2
`gather mechanism which allows large or small blocks of I/O
`transfer data to be scattered to or gathered from main
`memory. This mechanism cuts down on the number of
`processor interrupts required and the total number of I/O
`5 device interactions with the CPU when transferring large
`blocks of data. such as that required to support full motion
`video. Although the scatter gather programming interface
`specifications were originally intended specifically for con(cid:173)
`trolling hard disk drives on an IDE channel. software drivers
`10 can be written to access other types of storage devices on the
`IDE channel. storage devices on other types of J/O channels
`or network interface devices using the same homogeneous
`scatter gather programming interface.
`
`Description of Prior Apparatus
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates to computer system input output
`(I/0) operations. and more particularly to an apparatus and
`method for improving I/O performance of a multiple J/O
`channel computer system at minimal cost. This invention is 15
`intended for use in computer systems controlled by a mul(cid:173)
`FIG. l shows an apparatus used to perform bus master
`tiple tasking. multiple threaded operating system such as
`scatter gather DMA operations. The I/O control device 20
`Windows NT. OS/2. System 7 .5. Novell or UNIX. but could
`contains one or more descriptor table pointer registers 22. a
`also provide significant cost advantages in computer systems
`data manages 24. an I/O interface 26 and a CPU interface 28.
`controlled by single threaded and/or single tasking operating 20
`Each data manager 24 contains (i) a dedicated DMA engine
`systems such as Windows or DOS.
`for managing bus master data transfers between the I/O
`device (not shown) and main memory 30. and (ii) buffer
`2. Description of Related Art
`memory required for maintaining maximum data transfer
`A typical computer system generally includes one or more
`bandwidth between the I/O channel or interface bus 32 and
`central processing units (CPUs). main memory and one or 25
`the processor interface 28. The I/O control device 20 (also
`more J/O channels. The functions of the J/O channels are to
`known as an I/O controller) connects to the CPU 34 and
`transfer data between the CPU's main memory and either
`main memory 30 through a bridge 36. via interface 21. The
`storage units or network interface devices. Storage units
`bridge 36 may simply provide an extension of the proces(cid:173)
`store data and programs which the CPU uses in performing
`sor's bus. or may buffer and extend the processor bus using
`specific programming tasks. Typical storage units include 30
`an entirely different bus structure and protocol such as PCI.
`hard disk drives. CDROMs and tape drives. Network inter(cid:173)
`These types of bridges are commonly known in the art.
`face devices allow the transfer of data to or from other
`Besides containing CPU program and data storage. main
`computer systems on the network. Typical network inter(cid:173)
`memory 30 contains one or more physical region descriptor
`faces include ethernet. fiber channel. ATM and FDDI.
`35 tables 37 having entries 38. Main memory 30 allows storage
`Recently. applications run by the CPU have migrated
`of blocks of DMA data 40 transferred to or from the I/O
`toward using the high-performance processing power of
`devices on the I/O channel or interface bus 32. Data regions
`microprocessors (such as the Intel Pentium. PowerPC and
`40 represent blocks of linear DMA transfers of contiguous
`MIPs R4400) to generate real-time. full motion video. To
`double words of data. as specified by a respective entry 38
`support these applications, substantially more 1/0 bandwidth
`is required. Typically. full motion video windows are limited 40 in the physical region descriptor table 37.
`in size to a fraction of the video monitor size due to
`Description of Prior Method
`limitations in 1/0 bandwidth and or limitations in the pro(cid:173)
`cessing power of the CPU or video card. Users operating
`computer systems in multi-window. graphics intensive envi(cid:173)
`ronments expect instant response to mouse clicks or com- 45
`mands. Mouse clicks on an ICON representing a large text
`file or application should result in immediate visual results,
`whether or not the selected file resides on an J/O channel. or
`whether or not an J/O device is currently transferring large
`blocks of full motion video data. This instant response 50
`expectation. when coupled with the high-bandwidth transfer
`requirement. dictates that future J/O controllers allow I/O
`requests to be preempted and rescheduled at a later time.
`More recently. new techniques have been proposed for
`providing low-cost. high-performance J/O in the personal 55
`computer (PC) area. Enhanced IDE disk drives having large
`buffers. capable of interfacing to IDE channels having over
`sixteen megabyte per second DMA bandwidth. have been
`demonstrated and produced. and will likely become main(cid:173)
`stream in the PC industry over the next few years. Brad 60
`Hosler has proposed an IDE interface specification for
`improving system performance in multitasking
`environments. called "A Programming Interface for Bus
`Master IDE Controllers". which assumes the capabilities
`inherent in the DMA capable IDE disk drives mentioned 65
`earlier. Hosier's proposal. which is hereby incorporated by
`reference as background material. specifies a simple scatter/
`
`FIG. 2 shows a prior method used for performing I/O
`operations. At step 42. the CPU prepares a physical region
`descriptor (PRD) table in main memory. Each PRD table
`entry is 8 bytes long and consists of an address pointer to the
`starting address and the transfer size of the memory buffer
`to be transferred. The PRD table may contain up to 8192
`PRD table entries. with each entry specifying a single.
`contiguous block of data to be transferred between the I/O
`channel device and main memory. Sequential PRD table
`entries may specify that a block of data be transferred to or
`from any available location in main memory.
`At step 44. the CPU writes the starting address of the main
`memory physical region descriptor table to the I/O control
`device's descriptor table pointer register. The CPU writes
`the J/O controller's DMA transfer direction bit and clears
`appropriate J/O controller interrupt bits and error flags
`resulting from previous transfers.
`At step 46. the CPU issues the appropriate DMA com(cid:173)
`mand to the I/O device.
`At step 48. the CPU writes a start scatter gather command
`to the 1/0 controller.
`At steps 50. 52 and 54. the I/O controller performs a bus
`master scatter gather DMA operation by sequentially per(cid:173)
`forming all contiguous DMA block transfers between the
`
`Ex.1053.018
`
`DELL
`
`

`

`5.894.560
`
`3
`1/0 device and main memory as specified by the complete
`set of entries within a PRD table.
`At step 56, the 1/0 device signals that the requested data
`transfer is complete. The 1/0 controller signals the processor
`when all of the requested data has traveled through the 1/0 5
`controller's internal FIFOs and has been written successfully
`to either main memory or the 1/0 device.
`The 1/0 controller is usable for the next bus master DMA
`operation.
`
`10
`
`Reasons for Needing Improvement to Prior
`Techniques
`The apparatus previously described in FIG. 1 may be
`extended to allow multiple 1/0 channel bus master scatter 15
`gather operations. Clearly. by adding additional physical
`region descriptor (PRD) tables. "n" dedicated PRD tables
`may exist, one for each 1/0 channel to be managed by the
`1/0 control device. regardless of each 1/0 channel's protocol
`and function. so long as the IJO channel and it's associated 20
`1/0 devices are capable of DMA transfers. Furthermore.
`from one to "n" data managers may exist. whose function is
`to transfer data between the 1/0 devices residing on the "n"
`1/0 channels and main memory. Prior art implementations
`for performing these data transfers typically dedicate a 25
`single data manager to each 1/0 channel because the meth(cid:173)
`ods used to control the data managers are not successful in
`maintaining maximum possible J/O bandwidth between the
`1/0 devices and main memory. FIG. 3 shows single and dual
`data manager performance scenarios for a dual channel 30
`scatter gather JJO controller using the prior apparatus and
`methods just described. It should be noted that the 1/0
`channel is idle when the active J/O device's buffer has been
`emptied by the 1/0 channel DMA. The 1/0 channels shown
`in FIG. 3 perform at a bandwidth of twice the media rate of 35
`the 1/0 device. As FIG: 3 is otherwise self-explanatory to
`those of ordinary skill in the art. further description need not
`be given.
`Historically. 1/0 devices. due to the nature of their tech(cid:173)
`nology and their mechanical or network delays. are able to 40
`sustain data transfers at only 1/16 to 1/2 of the 1/0 bus
`bandwidth. Most 1/0 devices contain buffer memories (32 to
`256 K bytes in size) to compensate for their low media or
`network bandwidths. Thus, once the slow media rate has
`partially filled the devices buffer memory. IJO bus transfers 45
`may progress at data rates dictated by the faster bus band(cid:173)
`width rather than rates dictated by the slower media or
`network performance. However. once the buffer space has
`been exhausted due to a transfer which is larger than the
`buffer size, transfer bandwidth reverts back to the media or 50
`network bandwidth. It should also be noted in FIG. 3 that the
`prior method of performing DMAs does not efficiently
`utilize JJO device buffer memory during scatter gather
`operations. In fact. substantial media idle time and 1/0 bus
`idle time is incurred when using prior art methods with a 55
`single data manager and two IJO channels. The single data
`manager mechanism compromises the aggregate 1/0 perfor(cid:173)
`mance by requiring the completion of an 1/0 channel's PRD
`table prior to starting a bus master operation on the alternate
`channel. Dual data manager 1/0 controllers overcome these 60
`problems. but are expensive to implement due to their large
`FIFOs and complex DMA engines.
`In spite of numerous recent 1/0 related developments and
`proposals in the PC industry. additional capabilities are
`needed for achieving maximum 1/0 performance in multi- 65
`tasking. multi-threaded operating systems. at reasonable
`cost. The present invention provides an apparatus and
`
`4
`method for further improving computer systems 1/0 perfor(cid:173)
`mance at minimal cost.
`It is therefore an object of the present invention to provide
`an improved data processing system.
`It is another object of the present invention to provide an
`improved JJO operation in a data processing system.
`. It is yet another object to the present invention to provide
`Improved DMA operations in a data processing system.
`It is still another object of the present invention to provide
`improved DMA performance. at minimal incremental cost.
`in a data processing system.
`SUMMARY OF THE INVENI10N
`The present invention provides an apparatus and method
`for improving the input/output performance of a computer
`system under the control of a multi-tasking. multi-threaded
`operating system. In particular. the invention provides an
`apparatus and method to chain contiguous DMA scatter
`gather sub blocks of a PRD table for channel O with
`contiguous DMA scatter gather sub blocks of a PRD table
`for channel 1. using a single data manager. while maintain(cid:173)
`ing maximum media bandwidth. DMA block transfers are
`scheduled based on the availability of data from the 1/0
`device's buffer memory. thus minimizing both media or
`network idle time as well as minimizing J/O bus idle time.
`Near maximum aggregate bandwidth of multiple 1/0 buses
`and their associated devices is obtained. The apparatus and
`method thus provides significant performance advantages
`over prior techniques having two 1/0 channel systems
`implemented with a single data manager.
`The apparatus and method provides a means for preempt(cid:173)
`ing outstanding and inprogress DMA requests to an 1/0
`device on a given 1/0 channel when a higher priority request
`is encountered for a device on the same channel or for the
`same device.
`In a homogeneous programming interface environment as
`described previously. the invention can be easily extended to
`control "n+i" IJO channels using "n" data managers.
`The apparatus provides a performance efficient method
`for software drivers to make use of preemptive scheduling
`techniques found in newer multi-tasking. multi-threaded
`operating systems. Preemptive support lessens the response
`time of performance critical 1/0 requests.
`The details of the preferred embodiment of the present
`invention are set forth in the accompanying drawings and in
`the description which follows.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a diagram of a prior mechanism for performing
`bus master scatter gather DMA operations.
`FIG. 2 is a diagram of a prior method or fl.ow chart for
`performing bus master scatter gather DMA operations.
`FIG. 3 contains performance analysis diagrams for single
`and dual data manager. dual 1/0 channel operations.
`FIG. 4 is a diagram of the mechanism for performing
`single data manager controlled bus master scatter gather
`DMA operations in a two 1/0 channel system.
`FIG. 5 is a diagram of the method for performing single
`data manager controlled bus master scatter gather DMA
`operations in a two J/O channel system.
`FIG. 6 shows a method for merging concurrent interrupts.
`FIG. 7 shows a method for arbitration and selection by a
`data manager.
`FIG. 8 contains performance analysis diagrams for
`present invention single data manager. dual 1/0 channel
`operations.
`
`Ex.1053.019
`
`DELL
`
`

`

`5.894.560
`
`5
`FIG. 9 contains diagrams showing possible modes of
`operation suworted by the current invention.
`FIG. 10 is a block diagram of the preferred operating
`environment of this invention. using a PCI/Dual IDE 1/0
`channel control device.
`FIG. 11 is a block diagram of an alternate operating
`environment of this invention. using a PCI/Dual IDFJ
`ethernet 1/0 channel control device.
`
`DEfAil..ED DESCRIPTION OF THE
`PREFERRED EMBODIMENf
`
`Description of Preferred Apparatus
`
`6
`contiguous DMA block transfer available from either active
`IJO device. as specified by the associated PRD table entry
`for that channel. Following the above contiguous DMA
`block transfer. the data manager transfers a block from the
`5 alternate channel if data is available from the J/O device on
`that channel. H data is not available from the alternate
`channel, and data is available from the original channel, the
`data manager transfers a block from the original channel.
`Transfers continue in this manner so long as data is available
`10 on one of the two channels, and the current PRD tables have
`not been exhausted. If neither channel has data available for
`transfer. the data manager waits for the first available data
`transfer opportunity. Once data is available from either
`channel, the alternating channel DMA flow described above
`15 is restarted.
`At steps 156 or 157 (depending upon which channel is
`being used). the J/O device determines the transfer status,
`then signals that the requested data transfer is complete, The
`1/0 controller signals the processor when all of the requested
`20 data has traveled through the 1/0 controller's internal FIFOs
`and has been written successfully to either main memory or
`the 1/0 device. An J/O device on the alternate channel will
`continue operation following completion of a PRD table by
`the original channel.
`
`FIG. 4 shows the preferred awaratus. The 1/0 control
`device 120 contains a single data manager 124 and 1/0
`interface logic 126 which interfaces to two IDE 1/0 channels
`127 and 129. Main memory 130 contains two physical
`region descriptor tables 137 and 139 for controlling bus
`master DMA transfers on bus/channel 0 and bus/channel 1.
`A single PRD table is dedicated to each 1/0 channel. as
`shown at 121 and 123. The data manager 124 contains the
`necessary logic to chain DMA scatter gather blocks specified
`by PRD table entries between channels and between PRD
`tables in an alternating fashion. The data manager also
`contains the necessary logic to determine whether or not a 25
`target device on either channel contains DMA data ready for
`transfer. PRD tables 137 and 139 are not "swapped" by the
`data manager unless the alternate channel is prepared to
`transfer data.
`
`Description of Preemption Mechanism
`The preferred method provides the capability to non(cid:173)
`destructively preempt either bus master at any time during
`the transfer process. Two types of preemption exist. a
`30 preemption during mechanical or network delays prior to
`data transfer across the 1/0 bus. and preemption during
`active DMA data transfers. The first preemption (i.e. prior to
`data transfer) is detected at the 'Yes' exit point from block
`158 of FIG. 5. The second preemption (i.e. during active
`DMA data transfers) is detected at the 'Yes' exit point from
`blocks 154 and 155 of FIG. 5.
`During preemption, the process/program clears the start
`scatter gather command from the J/O control device for the
`preempted channel and evaluates the appropriate descriptor
`table pointer.
`If the pointer contains the address of the last PRD table
`entry from a previously executed PRD table. then the
`preemption is of the "prior to DMA" type. The process/
`program clears the active J/O device command, sends a new
`DMA command to the desired J/O device. rewrites the PRD
`tables. saves the current descriptor pointer register. rewrites
`the descriptor pointer register, and sends a new start scatter
`gather command to the 1/0 control device. When the pre(cid:173)
`empting PRD table has completed it's transfer, the previ(cid:173)
`ously saved descriptor pointer register is reloaded following
`the reissuing of the DMA command to the preempted 1/0
`device.
`H the pointer contains the address of any PRD table entry
`from the current PRD table. then the preemption is of the
`"during DMA" type. The process/program writes a "stop
`after current table entry" command to the 1/0 control device.
`The data manager will complete the current PRD table
`entry's DMA. then interrupt the processor.
`The process/program clears the active J/O device
`command, sends a new DMA command to the desired 1/0
`device. rewrites the PRD tables. saves the current descriptor
`pointer register. rewrites the descriptor pointer register. and
`sends a new start scatter gather command to the J/O control
`device. When the preempting PRD table has completed its
`65 transfer. the previously saved descriptor pointer register is
`reloaded following the reissuing of the abbreviated DMA
`command to the preempted 1/0 device.
`
`35
`
`40
`
`Description of Preferred Method
`FIG. 5 shows the preferred method used for performing
`1/0 operations. At steps 142 and 143, the CPU prepares a
`physical region descriptor (PRD) table in main memory.
`Each PRD table entry is 8 bytes long and consists of an
`address pointer to the starting address and the transfer count
`of the memory buffer to be transferred. The PRD table may
`contain up to 8192 PRD table entries. with each entry
`specifying a single. contiguous block of data to be trans-
`ferred between the 1/0 channel device and main memory.
`Sequential PRD table entries may specify that a block of
`data be transferred to or from any available location in
`memory. The two PRD tables may be prepared concurrently
`or sequentially.
`At steps 144 and 145. the CPU writes the starting address
`of the main memory physical region descriptor table to the
`1/0 control device's descriptor table pointer register. The
`CPU writes the 1/0 controller's DMA transfer direction bit
`and clears appropriate 1/0 controller interrupt bits and error
`flags resulting from previous transfers. The CPU may write
`either descriptor table pointer register at any time so long as
`the table to be written is not an active bus master.
`At step 146 or 147 (depending upon which channel is
`being used). the CPU issues the appropriate DMA command 55
`to an 1/0 device. A second 1/0 device on the alternate
`channel may be issued an additional DMA command con(cid:173)
`currently with the previously mentioned 1/0 device's DMA
`operation.
`At step 148 or 149 (depending upon which channel is 60
`being used). the CPU writes a start scatter gather command
`to one channel of the I/O controller. A second 1/0 control
`devices may be issued the start scatter gather command
`concurrently with the alternate channel's bus master opera(cid:173)
`tion.
`As shown in the remaining