United States Patent r191
`Fukushima et al.
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US005369744A
`5,369,744
`[11] Patent Number:
`[45] Date of Patent: Nov. 29, 1994
`
`[75]
`
`[54] ADDRESS-TRANSLATABLE GRAPHIC
`PROCESSOR, DATA PROCESSOR AND
`DRAWING METHOD WITH EMPLOYMENT
`OF THE SAME
`Inventors: Tadashi Fukushima; Shigeru Matsuo,
`both of Hitachi; Shoji Yoshida,
`Zama; Tooru Komagawa, Hitachi, all
`of Japan
`[73] Assignee: Hitachi, Ltd., Tokyo, Japan
`[21] Appl. No.: 596,366
`[22] Filed:
`Oct. 12, 1990
`[30]
`Foreign Application Priority Data
`Oct. 16, 1989 [JP]
`Japan .................................. 1-266142
`Oct. 16, 1989 [JP]
`Japan .................................. 1-266143
`[51]
`Int. Cl.s .............................................. G06F 15/20
`[52] U.S. CL .................................... 395/162; 395/163;
`395/400; 395/325; 364/230.2; 364/241.2;
`364/280.8; 364/927.92; 364/935.41
`[58] Field of Search ................ 395/162, 163, 164-166,
`395/275, 700, 800,325,400,425, 725; 340/798,
`799; 364/200, 900; 345/185, 200, 203
`References Cited
`U.S. PATENT DOCUMENTS
`4,376,296 3/1983 Anderson et al ................... 364/200
`4,737,909 4/1988 Harada ................................ 364/200
`4,791,580 12/1988 Sherrill et al ....................... 395/164
`4,860,192 8/1989 Sachs et al .......................... 364/200
`4,862,150 8/1989 Katsure et al ....................... 395/166
`4,967,374 10/1990 Nomura et al ...................... 395/150
`
`[56]
`
`FOREIGN PATENT DOCUMENTS
`62-62390 3/1987 Japan .
`
`63-91787 4/1988 Japan .
`2137857 10/1984 United Kingdom ................ 395/131
`
`OTHER PUBLICATIONS
`"Graphic Display Processor to Integrate Drawing Al(cid:173)
`gorithms and Display Controls" by Katsura et al, 8080
`Wescon Technical Papers Oct. 30-Nov. 2, 1984, LA,
`USA.
`Primary Examiner-Dale M. Shaw
`Assistant Examiner-Kee M. Tung
`Attorney, Agent, or Firm-Antonelli, Terry, Stout &
`Kraus
`ABSTRACT
`[57]
`In a graphic processing system, there are provided a
`main memory, a buffer containing a bit map memory for
`holding display data, a central processing unit for per(cid:173)
`forming a data process involving a translation from a
`virtual address into a physical address to access the
`main memory, a graphic processor connected to the
`main memory and buffer, for processing data into a
`display form, and a system bus interface connected to
`the central processing unit, main memory and graphic
`processor, capable of exchanging the data among them.
`Furthermore, the graphic processing system includes a
`drawing processing unit connected to the system bus
`interface, for translating the virtual address into the
`physical address to access the main memory and to
`process the data, a bus arbitrator for performing arbitra(cid:173)
`tion between demands for using the interface given
`from the central processing unit add graphic processor,
`and a suspend circuit for asserting a signal requesting
`that the interface is released to the central processing
`unit.
`
`43 Claims, 24 Drawing Sheets
`
`Petitioner Apple Inc. - Exhibit 1016, p. 1
`
`

`
`......... t
`~ -..
`CH
`-..
`en
`
`~
`~
`""""
`~
`00. go
`
`~
`""""
`\C
`~
`~
`
`""d I
`
`•
`00
`~ •
`
`207
`
`206
`
`205
`
`CONTROL
`
`CURSOR DATA •I CONVERTER
`
`I
`
`VIDEO
`
`LL OJ
`0:: ::>
`<t LL
`:::?: lL
`0:: ww
`
`CONTROL
`
`DATA
`
`l!> a..
`0:: 0::
`<{0
`:i::w a.u
`-(/')
`0 u (/')
`0::
`
`CONTROL
`
`DATA
`
`ADDRESS
`
`ADDRESS
`100
`
`21 I SYSTEM BUS
`
`210 ADDRESS BUS
`209 DATA BUS
`208 CONTROL BUS J
`FIG~ I
`
`HARD DISK
`
`MEMORY
`MAIN
`
`UNIT
`ARBITRATING
`BUS
`
`UNIT
`PROCESSING
`CENTRAL
`
`204
`
`203
`
`202
`
`201
`
`Petitioner Apple Inc. - Exhibit 1016, p. 2
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 2 of 24
`
`5,369,744
`
`SYSCLK
`
`A31~A2
`
`031-DO
`
`ADS#
`QUICK-'IF
`W/R#
`READY#
`
`CS#
`FS#
`
`HOLD
`HLDA
`BM#
`
`RES#
`SUS#
`IRQ#
`
`FIG. 2
`
`100
`
`GRAPHIC
`PROCESSOR
`
`VCC GND
`
`DISPCLK
`CLKOUT
`MAll"'-MAO
`
`MD3l"'-MDO
`
`RAS#
`CAS#
`WE#
`OT#/QE#
`OE#
`OS#'
`
`HSYNC-'IF
`VSYNC#
`DISP#
`
`CUR03"'-CURDO
`
`CURM3"'- CURMO
`
`CURDISP#'
`
`Petitioner Apple Inc. - Exhibit 1016, p. 3
`
`

`
`~ ... t
`... w
`
`(.II
`
`~
`e.
`w
`~
`~
`
`~ :
`~~
`~
`
`~ a
`L: • r.r.i •
`
`ti;
`
`CLOCK
`DISPLAY
`
`r
`,
`
`-(TO FB/VC/CRT)
`
`CONTROL
`
`,r
`11
`'
`,r :>CURSOR DATA
`
`(TO VC)
`
`,._.._,~ (FROM/ TO FB)
`
`DATA
`
`(TO FB)
`ADDRESS
`
`12
`106
`
`/
`
`.
`
`I
`
`GRAPHIC PROCESSOR
`
`FIG. 3
`
`1_
`
`I
`
`I
`
`_J -
`
`0 z
`u 1-
`<{ w
`_J a::
`LL
`<{
`ID U
`::) w
`
`(/)
`
`UNIT (CCU)
`CONTROL
`CRT
`
`UNIT (BCU)
`CONTROL
`BUS
`
`UNIT (MMU)
`MANAGEMENT
`MEMORY
`
`I
`
`I-
`
`UN IT (DPU)
`PROCESSING
`DRAWING
`
`104
`
`103
`
`102
`
`IOI
`
`(SBI)
`(/) -
`>-z
`(/) I(cid:173)
`I-w
`~~ w a::
`u
`IDw
`:::>
`(/)
`
`CLOCK
`SYSTEM
`
`12
`
`!FROM/TO CB)
`CONTROL
`
`!FROM/TO DB)
`DATA
`
`(FROM/TO AB>~
`ADDRESS
`
`?:D
`
`Petitioner Apple Inc. - Exhibit 1016, p. 4
`
`

`
`CH °' ~ ... t
`
`...
`UI
`
`~
`~
`0
`
`~
`
`~ -~
`
`~
`~
`~
`
`~
`
`~
`
`20
`
`'/V///j-I I 236 PHYSICAL
`
`ADDRESS
`
`... /
`
`/
`
`I
`
`0
`I
`2
`
`-.____.....-"""7 ~24 PIECES
`
`"'-232 ATTRIBUTE
`
`\
`
`20 BITS 12BITS
`
`( PTE l
`(PDE l
`ENTRY
`ENTRY
`TABLE
`DIRECTORY
`PAGE ~2 PAGE
`
`0
`I
`
`.
`
`.
`
`20 B\ITS 12 \ITS
`........____...
`
`2 31 PAGE ADDRESS
`
`229 PAGE TABLE
`
`ADDRESS
`
`230ATTRIBUTE
`20
`
`222
`
`?
`I I REGISTER I
`
`_
`
`~ S(cid:173)a
`•
`~ • 00
`
`PAGING MODEL
`FIG.4
`
`226 PAGE FRAME
`
`(4KBl
`
`1023
`
`225 PHYSICAL ADDRESS
`
`SPACE C4GBl
`
`I
`
`(4KBl
`
`224 PAGE TABLE
`
`C4KBl
`DIRECTORY
`223 PAGE
`
`I po23
`
`I
`
`12
`
`'1
`
`'f 10
`
`10
`
`I OFFSET
`
`DIRECTORY I PAGE
`
`0
`235
`
`234
`
`1221
`
`VIRTUAL ADDRESS
`
`31
`
`1233
`
`Petitioner Apple Inc. - Exhibit 1016, p. 5
`
`

`
`" t
`~ ...
`CH
`...
`en
`
`~
`e,
`sa.
`00 r
`
`(IJ
`
`~
`IC
`lo-I>
`
`~
`:id
`z Q
`
`""C a a
`
`•
`~ • 00
`
`DUPLICATE PAGE TABLE ENTRY 228
`
`I
`
`:
`
`.. l,I,/
`
`·228
`
`DIRECTORY
`PAGE
`
`I
`
`b IJ--__ __.,
`
`227
`
`1023.__ __ -'---1
`
`224
`
`234 PAGE
`
`IN DRAWING PROCESSOR
`ADDRESS TRANSLATION PERFORMED
`
`I 023,___ __ --o
`
`\
`223
`
`DIRECTORY
`233
`
`FIG.5
`
`PROCESS ING UNIT
`DRAWING
`
`IOI
`
`16
`
`241 LOGICAL ADDRESS
`
`236 PHYSICAL ADDRESS
`
`32
`
`OFFSET
`
`0
`
`PAGE ADDRESS
`31
`
`: -r-· ~
`I
`
`12
`
`20
`
`• • •
`
`0
`
`II
`
`12
`
`3231
`
`20
`
`51
`
`235
`
`0
`
`221 VIRTUAL ADDRESS
`
`OFFSET
`12-BIT
`
`PAGE
`10-BIT
`
`DIRECTRY.
`10-BIT
`
`32
`
`234
`
`31
`
`233
`
`:
`
`TAG
`
`311
`
`TABLE
`TRANSLATION
`ADDRESS
`242
`
`0
`
`Petitioner Apple Inc. - Exhibit 1016, p. 6
`
`

`
`~ t
`~ -..
`~
`-..
`en
`
`~
`e.
`Q\
`sa.
`00 go
`
`~
`--~
`~
`~
`
`~ • r.l'l •
`
`tD a
`~
`"'C
`
`1109
`
`I 107sus SWITCH"-1108
`
`~
`
`32
`
`(from/to SBI )
`DATA
`COMMAND/
`DRAWING
`301
`
`1017
`
`10051012
`
`MODE
`
`(to tvfv1U)
`3:.:0 o:: o ~ 3::: o o:: o 2 32 ADDRESS
`m 1 m 1 o:: m 1 en 1 ~ /.;;;{;:>DRAWING
`LL. r<>ll LL. r<>ll LL. 2 r<> 2 r<>
`
`::.:: ~ 302
`
`2u
`<to
`(/) z
`::ii:: 1-
`0::
`0
`_J
`
`_J
`::::>
`
`<tI men
`o:: \:!::
`0:: l(cid:173)
`WW
`_J 0::
`
`0:: LL.
`IB~
`~ w
`t-
`0:: w
`
`-1U -
`w 1- z Z _o
`
`Cf) 0::
`Oo
`l-o:: _J
`
`1003
`
`1002
`
`0:: LL. U_~
`0
`2
`2
`<t
`1001 I~
`
`t!) _J w_
`-w
`ti;
`ffi
`
`[;>304DRAWING
`
`(to LBI)
`I 32 1016 ADDRESS
`
`(from/to LBD
`DATA
`
`303
`
`.~
`;'
`I
`::::::;======:::::J
`1104
`\/32-
`rr==F{> DRAWING
`
`I
`
`\
`
`I
`
`I
`
`I
`
`1 I 1
`
`a I
`
`•
`1007
`
`(to MMU)
`t!f314MEMORY AccEss DEMAND
`
`316READ I WRITE (to MMU)
`315WAIT (from MMU)
`
`(toLBll
`i.=312 MEMORY ACCESS DEMAND
`
`313WAIT (from LBI)
`
`I
`
`MICRODECODER
`
`r1020
`
`.....c::J...
`
`LJ MICROPROGRAM ROM
`
`9
`
`\IOl
`
`.
`
`) I 1010
`
`1009
`
`1008
`
`1006
`
`-
`
`i
`
`7""""";:1 =-_--1-I ~I --.,
`3::: 8
`~ ~
`UJO::
`
`I I
`
`Bl¢
`I
`-cr
`
`CONTROL
`ADDRESS
`ROM
`
`1018
`
`10 21
`ADDRESS (from SBI)
`317 REGISTER
`(from SBI)
`WRITE ENABLE
`311
`
`I
`
`(to SBI) •
`COMMAND END
`316
`
`Fl G . 6 DRAWING PROCESSING UNIT DPU
`
`Petitioner Apple Inc. - Exhibit 1016, p. 7
`
`

`
`t
`.........
`~ ...
`t..)
`...
`U1
`
`r -...I e.
`
`.J:o,
`~
`
`~
`loC
`~ ....
`~
`
`~ a a
`~ • 00. •
`
`SELECT (TO SB I l
`413 WRITE
`
`41
`
`ACCES
`
`"2 IC::.
`(FROM DPUl
`316 READ/WRITE
`(FROM DPU)
`ACCESS DEMAND
`314 l'v1EMORY
`
`•• ·-·-
`
`'2do4
`
`\oMPARATo{ , 20. v2
`
`c.o
`~
`I-
`ii:
`w
`(/)
`
`<{0 ~
`a.. <{
`I-
`(.!)0
`w 0::
`a:
`w
`(/) m
`::>
`(/)
`I-
`w
`
`f 16
`
`;:!
`
`(!)
`
`2002
`
`f16 r20 v2t1
`
`0
`w
`(.)
`0
`0
`w
`0::
`
`c.o
`w
`z
`I-
`ii:
`w
`(/)
`
`2001 4
`
`2005
`
`CIRCUIT
`
`YcoNTROL
`
`.
`
`r
`
`f
`
`I E DR I
`r2011
`
`it ~ 403 PAGE REQUEST (TO SBI>-
`
`2101 407 READ/WRITE (TO 581 l
`
`410 DATA ACKNOWLEDGE
`" ""' .....
`
`(FROM SB I l
`
`32
`
`'-2010
`I
`2D {12
`
`I A R
`
`,
`32
`
`,
`
`A. <
`
`!FROM/ T
`402 DAT,
`
`~
`
`,,,..
`
`(TO SB I l
`ADDRESS
`PHYSICAL
`401
`
`s EL I
`
`)8 i-----.. -i s EL I
`
`20
`
`J2009t
`
`~
`
`~~ ~
`~ (.!)O
`I-
`0::
`wo::
`w
`ID
`::>
`I-
`w
`f4 f16. "20· "2
`
`(!)
`
`0
`w
`(.)
`0
`0
`w
`0::
`
`-
`
`-
`
`-
`
`(/)
`(/)
`
`F I G. 7 MEMORY MANAGEMENT UNIT MMU
`
`,-M coMPARAToFj 20 v2
`
`f 16
`I
`
`f
`
`2003
`
`.
`16
`
`PDBR 2007
`
`32
`VAR j
`
`0&
`
`- 2
`
`,
`32
`
`~~2012
`o::o
`I-I- -z
`
`w~ Q
`
`\ ~
`
`rER
`
`"1 DPUl
`IN(.; AUUHt:.::>::>
`
`(FROM SBI
`ADDRESS
`412 REGIS
`(FROM SBI
`ENABLE
`41j WRITE
`(FRO
`302 DRAW
`
`Petitioner Apple Inc. - Exhibit 1016, p. 8
`
`

`
`t
`... ......
`~ °' \C
`...
`
`(II
`
`~
`00 e.
`~
`~
`
`.f:o.
`~
`--~ .....
`'l4
`
`~
`
`I
`~ • 00. •
`
`~
`
`409 WAIT CTO MMU)
`
`40 6 MEMORY ACCESS
`
`<FROM MMU)
`DEMAND
`
`"'3006
`
`-
`
`F/F
`
`3005
`
`-
`
`ADJUSTMENT
`TIMING
`
`03004
`
`ADJUSTMENT
`TIMING
`
`l3003
`
`ADJUSTMENT
`
`I .
`
`ADJUSTMENT
`TIMING
`
`• TIMING
`
`504 BUS MASTER
`
`(TO SBI)
`
`<FROM SBI)
`
`503 SUSPEND
`
`(FROM SBI)
`502 HOLD RESPONSE
`
`501 HOLD DEMAND
`
`(TO SBI)
`
`408 BUS LOCK DEMAND
`
`( FROM MMU )
`
`'
`
`I
`
`I
`
`(3002
`
`-
`
`SEQUENCE CONTROL
`
`-
`
`3001
`
`BUS CONTROL UNIT BCU
`FIG.8
`
`Petitioner Apple Inc. - Exhibit 1016, p. 9
`
`

`
`~
`~
`-....l
`
`CH °' ._.\C
`...
`U1
`
`.i:;..
`N
`Q .....
`\C
`.....
`g'
`00.
`
`(!)
`
`~
`'" ...
`~
`~
`
`rJJ. •
`~ •
`
`'"'C i
`
`lO~
`o~
`C\Jw
`Cl(f)
`-(/)
`(/)~
`
`~~
`~...J
`m
`~ -
`
`22
`
`4009 \ 4011
`
`4010
`
`' J 4012
`
`4008 ' T J T \
`
`~
`
`BUS SWITCH
`
`4102
`
`So
`~ ttl
`Uw
`-u
`01-
`w
`z
`u
`w
`
`<t
`:::>
`
`u
`0
`:::>
`z
`~
`0::
`
`~ ()(/)<( >:C 0:: LL
`~t=!o
`ww w_
`(.!) ...J
`0 a...o::o 0::--w
`I-
`I-(.!)
`<1:-cn <1:1-~
`::r: _JI-~ ~:c
`>-Zen
`
`0::
`
`...J
`
`(.!)
`
`NO
`ww
`0:: I-
`OW
`u
`I-
`
`4101
`
`l
`
`C FROM SBI l
`4003
`CONTROL DATA
`601 ~ ""-4004
`
`4005
`u
`0
`::>
`z
`I-
`w
`0::
`
`I
`
`Cl..
`Cl..
`w (/) w
`0:: ~ 0::
`w
`0
`0
`0
`0
`4001"'> )
`4002
`
`W LL
`(.!) -
`-...J
`~
`0::
`
`>
`(/) 0::
`
`::r:
`en I en >
`~
`0
`I-
`::r:
`
`::r:
`
`(/)
`
`0
`I-
`J:
`----~
`
`I I~ I
`
`I
`
`SEQUENCE CONTROL FOR SYNC
`
`4017-1 SIGNAL SYSTEM
`
`::.=:..::.:..:~~~--1---~~~--if---+--+-~~---'
`
`4104
`
`4018
`
`S 81 )
`ADDRESS (FROM
`603 REGISTER
`(FROM SB I)
`ENABLE
`604 WRITE
`
`•I SEQUENCE CONTROL FOR DISPLAY
`
`ADDRESS SYSTEM
`
`~ .}
`n
`
`611 DISPLAY TIMING
`
`(TO LBI)
`
`(TO LB I )
`
`I
`
`I
`
`~
`
`1..
`
`4019
`F I G. 9 CRT CONTROL UNIT (CRT-CCU)
`
`--61 0 VERTICAL SYNC CONTROL
`
`WRITE
`
`SYNC (TO LBI l
`
`.------609 HORIZONTAL
`
`~a 1 coNTROL
`(TO LBI) ---=-i CURSOR
`
`(FROM LBI)
`608 DISPLAY CLOCK
`DATA
`607 cuRsoR
`
`( TO LBI J
`
`606 CURSOR DISPLAY
`
`32
`
`24
`
`6 12 CURSOR DATA
`POSITION( FROM SBI)
`613 CURSOR
`
`(FROM LB()
`
`Petitioner Apple Inc. - Exhibit 1016, p. 10
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 10 of 24
`
`5,369,744
`
`FI G . I 0 GRAPHIC PROCESSING
`
`PROCESSES BY CENTRAL
`PROCESSING UNIT 201
`
`PROCESSES BY GRAPHIC
`PROCESSOR
`I 00
`
`721
`I WAITING c.. I
`
`START
`
`701
`
`CALCULATE
`VIRTUAL ADDRESS
`
`SELECT PAGE TO
`BE LOCKED
`
`704\
`CALL LOCK
`~-~i _____ <~L..-R_o_u_T_IN_E __ ___.
`
`702
`
`703
`
`LOCK PAGE
`CRETU~
`~------'--,
`~<SET REGISTER)
`ISSUE
`DRAWING COMMAND
`
`705
`
`722
`
`INITIATE
`
`723
`
`EXECUTE DRAWING COMMAND
`
`706
`
`REPORT
`PROC
`
`REQUEST TO INVALIDATE
`TLB OF GRAPH! C
`PROCESSOR 100
`
`707
`
`SELECT PAGE TO
`BE UNLOCKED
`
`709
`
`UNLOCK
`PAGE
`
`(END
`
`)
`
`724
`
`725
`
`INITIATE
`
`727
`
`INVALIDATE TLB
`
`STOP
`
`728
`
`Petitioner Apple Inc. - Exhibit 1016, p. 11
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 11 of 24
`
`5,369,744
`
`FIG. 11
`EXECUTION OF DRAWING COMMAND
`
`750
`
`START
`
`INTERPRET
`DRAWING
`COMMAND
`
`FETCHING?
`
`YES
`
`752
`___ W_IT.....,HIN FRAME
`BUFFER 205
`
`WHERE ?
`WITHIN MAIN
`MEMORY 203
`
`CALCULATE
`PHYSICAL
`ADDRESS
`
`754
`FETCH PIXEL
`DATA FROM
`MAIN MEMORY 203
`
`755
`
`FETCH PIXEL
`DATA FROM
`FRAME BUFFER
`205
`
`756
`
`757
`
`758
`
`CALCULATE
`PHYSICAL ADDRESS
`
`759
`
`WITHIN FRAME
`BUFFER 205
`
`DRAW PIXEL DATA
`INTO MAIN
`MEMORY 203
`
`DRAW PIXEL DATA
`INTO FRAME
`BUFFER 205
`
`NO
`IS DRAWING
`~----------------1. PROCESS COMPLETED?
`YES
`END
`
`760
`
`Petitioner Apple Inc. - Exhibit 1016, p. 12
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 12 of 24
`
`5,369,744
`
`FIG 12 TRANSLATION INTO
`•
`PHYSICAL ADDRESS
`
`PROCESSES BY CENTRAL
`PROCESSING UNIT 201
`
`PROCESSES BY GRAPHIC
`PROCESSOR 100
`
`START
`
`801
`
`CALCULATE
`ADDRESS
`
`802
`SEARCH TLB HIS03
`
`804
`
`READ OUT
`PTE
`
`UPDATE PTE
`
`805
`
`810
`
`DOES PAGE
`AULT OCCUR?
`YES
`DEMAND
`PAGE
`
`821
`
`822
`
`CALL
`SWAPPER
`
`NO
`
`806
`
`FORM TLB
`ENTRY
`
`807
`UPDATE PTE
`IN ATTRIBUTE
`
`PAGE
`SWAPPING
`
`(RETURN)
`
`811
`
`,..........;:...__......_ __ .......
`823
`
`INITIATE
`GRAPHIC
`PROCESSOR I 00
`(SET
`REGISTER)
`
`UPDATE TLB 808
`ENTRY
`
`PRODUCE PHYSICAL
`ADDRESS FROM PAGE
`ADDRESS OF TLB AND
`OFFSET OF VIRTUAL
`ADDRESS
`812
`
`809
`
`INITIATE
`
`END
`
`Petitioner Apple Inc. - Exhibit 1016, p. 13
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 13 of 24
`
`5,369,744
`
`FIG 13 UPDATE OF PAGE
`•
`TABLE ENTRY
`
`PROCESSES BY CENTRAL
`PROCESSING UNIT 201
`
`PROCESSES
`PROCESSOR
`
`BY GRAPHIC
`100
`
`START
`
`CALCULATE VIRTUAL
`ADDRESS
`
`922
`
`925
`
`UPDATE
`PTE
`
`921
`
`REQUEST
`UPDATING
`
`COMPLETE
`INTERRUPT
`PROCESS
`
`REQUEST
`UPDATING
`
`COMPLETE
`INTERRUPT
`PROCESS
`
`CALL
`SWAPPER
`
`READ OUT
`
`903
`
`DEMAND FOR
`UPDATING PTE
`~~,,,.---...,...... 805 ---~-
`NO
`
`806
`
`FORM TLB
`ENTRY
`
`907
`DEMAND FOR
`UPDATING PTE
`808
`
`UPDATE
`TLB ENTRY
`
`DEMAND
`PAGE
`
`STOP
`
`SWAPPING
`
`811
`
`FORM PHYSICAL
`ADDRESS FROM PAGE
`ADDRESS OF TLB
`AND OFFSET OF
`CSET
`EGISTER l VI RT UAL ADD RESS
`
`INITIATE
`GRAPHIC
`PROCESSOR
`100
`
`809
`
`END
`
`Petitioner Apple Inc. - Exhibit 1016, p. 14
`
`

`
`·-
`
`DISPLAY
`CONTROL
`SIGNAL
`
`CONTROL
`ADDRESS
`DATA
`
`CONTROL
`
`ADDRESS
`
`DATA
`
`CS#
`FS#
`
`HOLD
`HLOA
`BM#
`
`a:::
`0
`(/)
`
`(/) w u
`0 a:::
`a.
`
`A
`
`'\.
`
`1--
`
`-1\
`
`,A
`
`..
`
`.__
`lu
`
`i - -
`
`I'- ....__
`
`I'-
`'r
`
`208 210
`'200
`,. ~- -:_J
`-
`r - ---
`)
`µ-_ -
`"
`f-,1 -
`..
`- ':'-JI
`...
`.
`- ----- -' -
`••
`.,
`-
`1 DECODER
`----
`a::: N202
`-
`.....J ~ ~ ----
`0
`t-
`0 ---- I~ .__ ~ <t
`a:::
`a:::
`201
`t-
`:~
`I~
`t-
`z
`\
`I~
`Cf) CD
`HOLD
`0
`::> a:::
`u
`HLOA
`CD <t
`'\r- --
`.
`....__ - GENERATING
`"
`r--.... RTE
`CIRCUIT
`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 14 of 24
`
`5,369,744
`
`I 00
`
`FI G 14 SYSTEM ARRANGEMENT
`.
`
`206
`L----1
`
`207
`r1
`
`·, :..
`
`r
`
`\...
`
`'
`
`~
`
`,.
`
`.
`
`r
`
`205
`FRAME
`.....J
`.
`~ BUFFER
`<t(9
`zz
`CONTROL
`(9-
`r---. en~ t- f---"
`DISPLAY
`ADDRESS ~ 0:::3 ~ UNIT
`.
`Owu
`Wza:::
`DATA
`Qw_
`><9U
`r203
`
`.
`"
`
`"
`.
`
`r
`
`CONTROL
`MAIN
`ADDRESS MEMORY
`DATA
`
`211
`
`CONTROL
`
`r
`
`ADDRESS
`~ DATA
`MPU
`INT INTA
`
`r
`
`()
`I
`I
`I
`I
`LEVEL
`" CONTROL
`.
`ADDRESS
`.
`
`1213
`
`r
`
`h: .....J
`::> 0 t-
`O:::a:::-
`a::: t- ::>
`~z~
`zO-
`DATA
`-UU
`1 f . . . f
`n
`0
`I
`INTERRUPT SIGNAL
`
`214
`212
`
`z
`0
`i-- u
`SUS#
`
`t-
`~::>
`(/) u
`::>~
`(/) u
`
`-
`
`IRQ#
`I
`
`>[; -
`a::: - -
`t- - ....__
`- -
`-
`- - ....
`
`....__
`,___
`,___
`
`....__
`
`,__
`
`.
`..
`SYSTEM BUS
`
`._
`
`Petitioner Apple Inc. - Exhibit 1016, p. 15
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 15 of 24
`
`5,369,744
`
`~(.!)
`
`UJ
`(.)
`
`a:
`0 en en
`0 a: a..
`c zu
`<C:E
`za..
`o< _a:
`(f)>-
`=>a:i
`0
`U<f>
`<C<f>
`>-w
`~(.)
`_u
`a::<C
`0 ->-
`a::a::
`a..o
`en::!:
`:::>W
`CD::!:
`
`LO
`-
`-l.J...
`
`(!)
`
`I-
`en
`<(
`_J
`
`I-
`en
`a:
`l.J...
`
`w
`_J
`u
`>-u
`en
`::::>
`CD
`
`w
`w...J
`_Ju,______
`o>-
`-U
`
`~
`
`_J
`<{~ r<)
`_J Zu <{
`u o:::o
`W_i N
`r-u <{
`Cf)
`Cf) -
`z
`>-
`
`0
`_J
`0
`I
`
`<{
`0
`_J
`I
`
`~
`~
`CD
`
`Petitioner Apple Inc. - Exhibit 1016, p. 16
`
`

`
`....:I :t
`~ ...
`...
`
`(Jo)
`(JI
`
`~
`Q ....,
`c:I'\
`.....
`m.
`~
`
`olloo
`~
`--~ .....
`~
`
`~ a a
`~ • 00
`
`•
`
`PROCESSOR
`... • OF GRAPHIC
`
`I BUS CYCLE
`
`BUS CYCLE OF MPU
`
`•
`I
`
`•
`
`GRAPHIC PROCESSOR
`BUS CYCLE OF
`
`PROCESSOR
`SYSTEM BUS BY GRAPHIC
`MPU AGAIN PERMITS USE OF
`
`SYSTEM BUS
`PROCESSOR TO RELEASE
`MPU DEMANDS GRAPHIC
`
`"'GRAPHIC PROCESSOR RELEASES
`
`SYSTEM BUS AND STOPS
`
`< --~>
`
`"---~
`
`l'
`
`!'
`
`SUS#
`
`BM#
`HLDA
`HOLD
`
`A2-A31 ----1'
`CLOCK
`
`INTERNAL
`
`Fl G.16 OCCURRENCE OF INTERRUPTION TO MPU WHILE SYSTEM, BUS
`
`IS USED BY GRAPHIC PROCESSOR
`
`. '
`
`Petitioner Apple Inc. - Exhibit 1016, p. 17
`
`

`
`-...l :t
`...
`$
`(H
`...
`C.11
`
`~
`~
`~ .......
`a
`g'
`00.
`
`~
`'.e
`'.e
`~
`
`z Q
`
`~'.e
`N
`;<!!
`
`"'C a a
`
`• en •
`(j
`
`~
`
`I
`~~~~~
`
`-----1
`
`I
`l~w\\\I~
`~
`
`~ ,_____
`
`)
`
`OUT
`
`I
`
`~
`
`
`-~
`
`I
`
`DO-D31
`
`READY#
`
`W/R#
`
`ADS#
`
`A2-A31
`
`CLOCK
`INTERNAL
`
`SYSCLK
`
`T3 T4 IT! T2 T3 T4 T4W T4WI
`
`Tl T2
`
`( 2WAIT)__
`
`READ CYCLE
`
`CYCLE
`
`WRITE
`
`BY GRAPHIC PROCESSOR
`FIG. 17 ACCESS TO MAIN MEMORY
`
`Petitioner Apple Inc. - Exhibit 1016, p. 18
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 18 of 24
`
`5,369,744
`
`FIG. 18
`CONTROL OF SUS# SIGNAL
`
`100
`\
`
`SUS#-(cid:173)
`GRAPHIC
`PROCESSOR
`
`214
`~
`RTE GENERATING
`RTE CIRCUIT
`
`201
`/
`'v ' /
`DATA- BUS
`ADDRESS-BUS
`...----+---___, I NTA
`
`MPU
`
`INT
`
`212 /"\.
`
`SUS# lNTA RTE
`
`SUS#
`CONTROL
`CIRCUIT
`INT
`
`213
`~
`
`INT
`INTA
`INTERRUPT
`CONTROL CIRCUIT
`
`INTERRUPT SIGNAL
`GROUP
`
`Petitioner Apple Inc. - Exhibit 1016, p. 19
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 19 of 24
`
`5,369,744
`
`FIG. 19
`SUS# SIGNAL CONTROL LOGIC
`
`212
`
`INT ---'-----------.
`2121
`
`INTA _._-~s
`FF D 1--------1
`R
`
`RTE
`
`FIG. 20
`SUS# SIGNAL CONTROL
`
`INT
`
`INTA
`RTE
`SUS#
`
`SUS# WREN
`MPU DOES NOT
`ACCEPT INT
`
`\
`
`r-
`
`\
`
`Petitioner Apple Inc. - Exhibit 1016, p. 20
`
`

`
`.....,J :t
`(N °' \C
`
`....
`
`....
`OI
`
`~
`s,
`~
`m.
`1:1"'
`00
`
`~
`~
`~
`
`i-
`
`a
`"'C ;.
`•
`00
`L! •
`
`SUS# SIGNAL
`NEGATE
`
`SUS# SIGNAL
`NEGATE
`
`SUS,, SIGNAL
`NEGATE
`
`PROCESS n
`URGENT
`
`START
`
`•••
`
`START
`
`START
`
`/r___.__ --------
`
`2
`
`PROCESS
`URGENT
`
`I
`
`PROCESS
`URGENT
`
`/
`
`PROCESS
`NORMAL
`
`INTERRUPT
`EXTERNAL
`
`INTERRUPT
`
`SELECTION MADE BY SORT OF
`
`START
`
`'
`
`I
`
`PLURAL INTERRUPTS
`FIG. 21 MPU FOR ACCEPTING
`
`END
`
`•••
`
`I
`
`END
`
`END
`
`END
`
`~
`
`' RETURN
`
`Petitioner Apple Inc. - Exhibit 1016, p. 21
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 21 of 24
`
`5,369,744
`
`FIG. 22 ASSERTING IRQI SIGNAL
`BY SUSI SIGNAL
`
`214
`
`RTE GENERA TING
`RTE CIRCUIT
`/\ /'\
`
`1008
`;
`
`SUS#...____
`
`201
`r-1
`v
`\,1
`DATA- BUS
`ADDRESS- BUS
`
`--------1 INTA
`
`GRAPHIC
`PROCESSER
`
`IRQ#
`
`SUS11 INTA RTE
`SUS1t CONTROL
`CIRCUIT
`
`INT
`
`~
`212
`
`MPU
`
`INT
`
`2138
`;
`
`INT
`INTA
`INTERRUPT CONTROL
`CIRCUIT
`
`INTERRUPT SIGNAL
`GROUP
`
`Petitioner Apple Inc. - Exhibit 1016, p. 22
`
`

`
`~ S(cid:173)a
`
`•
`00
`~ •
`
`SELECTION MADE BY SORT OF INTERRUPT
`
`START
`
`FIG.23 NEGATING PROCESS OF
`
`SUS# SIGNAL
`
`Petitioner Apple Inc. - Exhibit 1016, p. 23
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 23 of 24
`
`5,369,744
`
`IOOC
`?
`
`GRAPHIC
`PROCESSOR
`
`FIG. 24 NEGATING OF
`SUSI SIGNAL
`
`201
`
`/
`
`.------...........i INTA
`
`MPU
`
`INT
`
`SUS# INTA RTE
`SUS# CONTROL
`CIRCUIT
`
`INT
`
`~
`212
`
`214C
`\
`
`RTE
`RTE GENERATING
`CIRCUIT
`
`------i
`<
`J
`INTERRUPT
`LEVEL
`
`213C
`/
`
`INT
`
`INTA
`INTERRUPT
`CONTROL CIRCUIT
`
`INTER RUT
`SIGNAL GROUP
`
`Petitioner Apple Inc. - Exhibit 1016, p. 24
`
`

`
`U.S. Patent
`
`Nov. 29, 1994
`
`Sheet 24 of 24
`
`5,369,744
`
`FIG. 25
`NEGATING PROCESS FOR
`SUSI SIGNAL BY MPU
`
`100 ;
`
`2010
`I
`
`SUS# ..-.----.
`
`r - - - - - - - e - - - - -1 INTA
`
`GRAPHIC
`PROCESSOR
`
`.-------i RTE
`
`MPU
`
`INT
`
`SUS# INTA RTE
`
`SUS# CONTROL
`CIRCUIT
`
`)
`2120
`
`INT
`
`INTA
`INTERRUPT
`CONTROL CIRCUIT
`
`2130
`I
`
`INTERRUPT SIGNAL
`GROUP
`
`Petitioner Apple Inc. - Exhibit 1016, p. 25
`
`

`
`1
`
`5,369,744
`
`30
`
`ADDRESS-TRANSLATABLE GRAPHIC
`PROCESSOR, DATA PROCESSOR AND DRAWING
`MEfHOD WITH EMPLOYMENT OF THE SAME
`
`2
`characters on the bit map. Another Japanese patent
`publication JP-A-63-91789 discloses the graphic proces(cid:173)
`sor for transferring the bit map data between the main
`memory and frame buffer in order to display the multi-
`5 window.
`There is a problem that a lengthy data processing
`BACKGROUND OF THE INVENTION
`time is required for the bit map data when the central
`The present invention relates to a data processing
`processing unit solely accesses the main memory. To
`apparatus for processing bit map data, a method for
`achieve highspeed data processing, the graphic proces-
`processing the bit map data in this data processing appa-
`ratus, and a graphic processor for constituting process- 10 sors which are exclusively used for processing the bit
`ing method, and also a graphic processing system.
`map data have been invented. However, no specific
`In conventional data processing apparatuses, the fol-
`care has been taken for such a case that the main mem-
`ory is virtually formed in the conventional graphic
`lowing two methods have been employed when bit map
`data stored into a main memory is processed. Accord-
`processors. As previously described, the drawing in-
`ing to one method, a central processing unit directly 15 struction must be given in a unit of address space contin-
`accesses the main memory so as to update the bit map
`ued on the main memory for these graphic processors.
`data. In accordance with the other method, a graphic Moreover, care must also be taken that the data to be
`processed is continuously present in the main memory
`processor used exclusively used for processing the bit
`map ~ata is p~epared, and_ the main memory is ac~essed
`undergoing the accessing operation to the main mem-
`by this grap~c pr~cessor m o~der to update ~he ?1t map 20 ory by the graphic processors. To perform the above-
`data, as descnb~d m ~he pendmg patent application Ser.
`described processings, the workload of the drawing
`No. 9?,5, 173 entitled GRAPHIC PROCESSING SYS-
`process given to the central processing unit cannot be
`TEM , filed by K. Katsura et al. on Sep. 9, 1986, the
`sufficiently reduced which may cause the overall per-
`formance of the da~ processor to be lowered There
`disclosure of which is incorporated herein by reference.
`In th~ first-mentioned method, ifthe address.space of 25 have been proposed two methods for using the. system
`t~e mam memory has not yet been m.ade vt_rtual or
`bus. That is to say, in accordance with the first method,
`virtually proc~ssed, the central processmg umt calcu-
`when the data transfer unit such as the direct memor
`llin
`.
`'
`lates the physical address of the data to be processed
`y
`d
`thi d ta T
`th
`t
`"f th dd
`access contra
`g umt, performs the data transfer oper-
`· oh ebcon virtualr~, 1
`e a
`. s a
`redss
`an accfethsses
`ation with the main memory for storing therein the
`e mam memory as een
`y processe ,
`b
`.
`1
`space o
`d . fi t
`processed data y employmg the system bus, once the
`e a
`o e processe
`e
`a
`ress o
`IS rrs
`.
`.
`.
`f th d ta t b
`th virtual dd
`data _transfer operat~on is c?~enced, the system bu~ is
`calculated by the memory management unit employed
`~ontmuously <;>ccup1ed until this data transfer operation
`by the central processing unit, and the main memory is
`IS ~ompleted (1.e., burst transfer method~. In accordance
`accessed after this virtual address is translated into the
`physical address. At this time, if no data to be processed 35 with the se~ond ~ethod, the occupation rate of the
`syst~m bu~ is previously set, and ~JOth the central pro-
`is present in the main memory, the central processing
`cessmg umt _and data transfer umt alternately use the
`unit accesses this data after the necessary data has been
`read out from the secondary storage unit and supplied
`system bus (1.e., cycle steal method.)
`In the burst t~ansfer method, there is a small soft:""are
`to the main memory.
`On the other hand in the latter-mentioned method 40 overhead to arbitrate the system bus and also the higher
`the graphic process~r accesses the main memory ~ d~ta transfer efficiency can be expected, as ~ompared
`accordance with the instruction from the central pro-
`with the cycle steal method: How~ver, there is a prob-
`cessing unit. At this time, only typical points of the data
`lem that the central processmg umt cannot execute the
`to be processed are designated by the physical informa-
`process until the processing operation by the data trans-
`tion of the main memory. In other words, existence of 45 fer unit is accomplished in the case when the central
`the respective data to be processed has been calculated
`processing requires performance of the urgent process-
`by employing the internal calculating circuit by the
`ing operation during the data transfer operation by the
`graphic processor based upon the information on the
`data transfer unit due to external reasons and internal
`given typical points. Since the address information of
`reasons of the system. There are further problems that
`the typical points given to the graphic processor corre- 50 the construction of the bus arbitrator becomes complex
`spond to the physical address, the address information
`and also a cumbersome procedure is required to restart
`on the respective data to be processed, which is calcu-
`the system after the data transfer operation by the data
`lated by the graphic processor, similarly corresponds to
`transfer unit is interrupted, and the central processing
`the physical address, so that the graphic processor can
`unit occupies the system bus so as to perform the pro-
`directly access the main memory without using the 55 cess corresponding to the interrupt.
`central processing unit. At this time, if the address space
`On the other hand, in the cycle steal method, the
`of the main memory has not yet been virtually pro-
`central processing unit can temporarily execute the
`cessed, no specific care is required. To the contrary, if
`process of the data transfer operation. However, there
`the address spaGe of the main memory has been virtu-
`is such a problem that the software overhead for acquir-
`ally processed, the central processing unit must instruct 60 ing the system bus by the central processing unit be-
`the graphic processor to perform the drawing operation
`comes large, the data transfer efficiency is lowered, and
`in a unit of the address space continued on the main
`also a lengthy processing time is required, as compared
`memory. Also, when the main memory is undergoing
`with the burst transfer method. These problems may be
`accessing operation by the graphic processor, a care
`similarly applied to such a data transfer operation be-
`must be taken such that the data to be processed contin- 65 tween a main memory and frame buffer, and also to a
`uously exists on the main memory.
`drawing processing operation by a main memory hav-
`In one Japanese patent publication JP-A-62-62390,
`ing the condition that a data transfer unit is substituted
`there is disclosed the graphic processor for drawing
`by a graphic processor.
`
`Petitioner Apple Inc. - Exhibit 1016, p. 26
`
`

`
`25
`
`3
`SUMMARY OF THE INVENTION
`An object of the present invention is to eliminate such
`a requirement that a central processing unit instructs a
`drawing to a graphic processor in a unit of continuous 5
`address space on a main memory.
`Another object of the present invention is to provide
`a graphic processing system capable of transferring
`multiwindow display data stored in a main memory to a
`bit map memory at a high speed so as to be output to a 10
`display.
`Another object of the present invention is to provide
`a data processing apparatus in which a graphic proces(cid:173)
`sor translates a virtual address of a vertical memory into
`a physical address, and a central processing unit enables 15
`the graphic processor to perform a drawing process
`which corresponds to a data transfer unit between a
`main memory and a secondary storage unit and also
`bridges plural blocks by way of a single instruction.
`Another object of the present invention is to provide 20
`a memory management capable of performing a high
`speed data transfer operation between a main memory
`and a frame buffer of a data processing unit for support(cid:173)
`ing a virtual storage without employing a memory man-
`agement function by a central processing unit.
`A further object of the present invention is to provide
`a drawing method, a data transfer method, a graphic
`processor for realizing this method and a data process(cid:173)
`ing unit in which a small software overhead is realized,
`a high data transfer efficiency is realized, and also a 30
`construction of a bus arbitrator is made simple.
`A still further object of the present invention is to
`provide a display data processing method and also a
`system thereof wherein a graphic processor accesses a
`main memory, and since the graphic processor detects 35
`an occurrence of interruption to an MPU while access(cid:173)
`ing a system bus and also releases the system bus, after
`both a drawing process and a data transfer operation are
`interrupted and the MPU executes the process, the
`original process can be restarted without any assistance 40
`from software and thus use efficiency of the system bus
`can be improved.
`Another object of the present invention is to provide
`a graphic processor, a data processing apparatus for
`utilizing the same, and also a drawing method in which, 45
`while a graphic processor accesses a main memory, no
`care need be taken such that data to be processed is
`continuously present in the main memory, and also a
`workload of the drawing or graphic data process given
`to a central processing unit is reduced, so that the over- 50
`all performance of the data processing unit is increased.
`To achieve the above-described objects, a major fea(cid:173)
`ture of the present invention is as follows. An address
`translation table for translating a virtual address into a
`physical address is built in a graphic processor; a mech- 55
`anism is provided for performing, by itself, updating of
`the content of this address translation table; and further(cid:173)
`more when data to be processed is present in a main
`memory, such a-mechanism is employed that a demand
`for reading this data from a secondary storage unit and 60
`supplying this data to the main memory is made to the
`central processing unit.
`The graphic processor accesses the bit map data on
`the main memory in accordance with the instruction
`given from the central processing unit. At this time, as 65
`to the data to be processed, only typical or, representa(cid:173)
`tive points thereof are instructed by the logical address
`information. If the address space of the main memory
`
`5,369,744
`
`4
`has been virtually formed, the graphic processor calcu(cid:173)
`lates locations of the respective data to be processed as
`the virtual addresses based upon the contents of the
`drawing instruction and this logical address informa(cid:173)
`tion. At this time, if the physical address information
`corresponding to this virtual address is not present
`within the address translation table, this fact is reported
`to a bus arbitration controlling unit which will arbitrate
`a bus access right or bus access priority with another
`bus arbitrator employed at the system so as to obtain
`such a bus access right. Thus, the graphic processor per
`se accesses the main memory to update the content of
`the address translation table, whereby a physical ad(cid:173)
`dress of the data to be processed is obtained. When it is
`recognized that no data is present to be processed in the
`main memory during the content updating operation of
`the address translation table, the graphic processor re(cid:173)
`quests the central processing unit to read out the bit map
`data containing the data to be processed from the sec(cid:173)
`ondary storage unit and supply this bit map data to the
`main memory. After the bit map data reading operation
`has been completed, the graphic processor updates the
`content of the address translation table. After the con(cid:173)
`tent of the address translation table has been updated
`and the physical address of the data to be processed has
`been acquired, the bus arbitration controlling unit
`newly arbitrates with the bus arbitrator employed at the
`system side so as to establish the bus access right, and
`performs the drawing process to the bit map on the
`main memory based upon the above-described physical
`address.
`With the above-described process operation, even
`when the main memory has been virtually formed, after
`receiving the drawing instruction from the central pro(cid:173)
`cessing unit, the graphic processor can perform the
`drawing process on the bit map of the main memory
`without requesting the memory management function
`of the central processing unit. In other words, even
`when the address space of the main memory has been
`virtually formed, the central processing unit no longer
`must instruct the graphic processor to perform the
`dra