JAIST Reposi https://dspace.j Title ページアドレス予測による TBL プリローディングの研究 Author(s) 請園, 智玲 Citation Issue Date 2003-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/1700 Rights Description Supervisor: 田中清史, 情報科学研究科, 修士 Japan Advanced Institute of Science and
TLB 2003 3
TLB 110019 : 2003 2 Copyright c 2003 by Ukezono Tomoaki 2
TLB TLB TLB TLB
1 1 2 3 2.1.............................. 3 2.1.1................................. 3 2.1.2.................. 4 2.1.3.......... 6 2.2.................................. 9 2.2.1................... 11 3 15 3.1 Wide Range Support.............................. 15 3.1.1 WRS................... 16 3.1.2................ 19 3.1.3 WRS.......... 21 3.2 Multiple Operand Support........................... 26 3.2.1.............................. 27 3.2.2 MOS..................... 28 3.3 WRS MOS........................ 31 3.3.1........ 31 3.3.2...... 32 4 33 4.1 [Integer Unit]..................... 34 4.2 MMU...................................... 35 4.2.1 MMU................................ 35 4.2.2 TLB................................... 39 5 42 5.1......................... 42 5.2.................................. 42 i
5.2.1............................. 43 6 44 6.1............................. 44 6.1.1.......................... 44 6.1.2................................. 46 6.2..................................... 47 7 48 8 49 ii
2.1........................... 5 2.2........ 6 2.3............. 7 2.4 PPTE PTE.............................. 10 2.5........................... 12 2.6......................... 13 3.1 Wide Range Support WRS........................ 16 3.2 WRS..................... 17 3.3 WRS.......... 20 3.4 2WRS............................ 22 3.5... 23 3.6 24 3.7 Multiple Operands Support MOS.................... 26 3.8 4MOS......................... 29 3.9 MOS......................... 30 3.10 WRS MOS.............. 32 4.1...................... 33 4.2....................... 34 4.3 MMU............................ 36 4.4 MPSR.............................. 38 4.5 TLB....................... 39 4.6 TLB.................................. 41 5.1 1.............................. 43 8.1............................. 51 iii
3.1 8 2............. 19 4.1 0...................... 37 4.2 MIPS R3000............. 37 4.3 MIPS R3000 Attribute....... 40 6.1............................ 45 6.2.................................. 46 iv
1 1. 2. OS 3. 4. OS OS TLB Translation Lookaside Buffer TLB TLB 1
TLB TLB TLB TLB 12.5% 20% [1] TLB TLB TLB [2] subblock TLB[3] TLB TLB TLB TLB 2 3 4 CPU 5 6 7 8 2
2 2.1 2.1.3 2.2 TLB 2.1 2 2.1.1 ( ) SRAM 2 1 1 PC(Program Counter) 3
2 32 4KB 1 1/1024 2 1 1 TLB LRU( ) [1] 2.1.2 2.1.2 ( ) 1 4
2 2.1 ªªª u ªªª preload preload ªªª +1 Last Hit PTE -1 ªªªªªªª TLBªªªªªªªª TLB 2.1: ( 3 TLB ) TLB ±1 PTE TLB 2 3 5
PTE TLB 2.2 2.1.3 2.2 2.2: Predictor Control Unit Prediction Address Generator Buffer Refill Selector 3 6
Refill Canceler Status Register 2.2 Predictor Control Unit Status Register Prediction Address Generator Predictor Control Unit VPN(Virtual Page Number) Last Hit PTE RRP VPN( Reamer Reference Position Virtual Page Number ) ±1 VPN VPN AS( Address Strobe ) TLB Buffer Refill Selector Predictor Control Unit Predicted VPN Predicted PPN( Physical Page Number ) TLB Hit VPN TLB Hit PPN (PTE) 2.3 2.3: 7
2.2 T 0 T 6 T 0 (PTE : Page Table Entry) T 1 PTE RRP RRP Data RRP Write Enable TLB T 2 TLB TLB Last Hit PTE TLB TLB PTE TLB (T 1 T 2) TLB TLB TLB PTE T 2 TLB TLB TLB Hit VPN TLB Hit PPN ACK PTE T 3 TLB Hit VPN TLB Hit PPN VPN VPN+1 VPN 1 T 3 VPN+1 VPN Out VPN TLB TLB PTE T 4 VPN+1 PTE Predicted VPN Predicted PPN PTE T 5 T 4 T 3 VPN 1 T 6 2 VPN PTE TLB (T 1 T 2 T 3 T 4 T 5 T 6) 3 12 CPU 10 20 120 240 PTE 8
VPN±1 TLB Last Hit PTE 2.2 PTE PTE TLB 3 1 PTE PTE LRU TLB PTE 2 TLB PTE PTE PTE PTE 2.1.2 PTE PTE PPTE Pointer Page Table Entry PTE PPTE PPTE TLB PTE PPTE PPTE PTE TLB PPTE 9
ªªª PPTE PPTE(Pointer Page Table Entry) Ç Ç Ç Ç Data set A PPTE Data set B PPTE Data set C PPTE PTE ªªª ªªªªª «««T L B PPTE PPTE PPTE 2.4: PPTE PTE 2.4 A B C TLB PPTE 3 TLB PTE PPTE TLB TLB 3 PTE TLB 3 1 TLB 1 TLB 32 TLB TLB 35 TLB 1 TLB PPTE 3 10
PPTE 3 TLB TLB Split TLB 4 TLB Shard TLB 5 TLB 2.2.1 TLB TLB TLB TLB 2.5 4 TLB TLB 5 TLB TLB MIPS TLB TLB TLB 2 TLB 11
2.5: Last Hit PTE ±1 PTE 3 1 PTE VPN PPN, Attribute TLB Valid RRP 6 RRP 2.2.1 RRP PTE 2.6 6 MIPS Dirty Valid Attribute Dirty Attribute 12
d +1 ªªª -1 ªªª VPN=97 VPN=97 VPN=97 RRP VPN VPN=98 VPN=99 VPN=100 VPN=98 VPN=99 VPN=100 VPN=98 VPN=99 VPN=100 VPN=101 VPN=101 VPN=101 VPN=102 VPN=102 VPN=102 VPN=103 VPN=103 VPN=103 ªªª RPP BIT +1 ªªª RPP BIT -1 ªªª RPP BIT 100 VPN=99 010 VPN=102 Refill 001 VPN=99 RRP VPN 001 VPN=100 100 VPN=100 010 VPN=100 010 VPN=101 001 VPN=101 Refill 100 VPN=98 2.6: VPN VPN VPN=100 VPN VPN=97 VPN=103 VPN=100 RRP VPN ±1 VPN=101 VPN=99 +1 VPN=101 VPN=101 RRP VPN -1 VPN=99 (RRP ) RRP (RRP) VPN+1 VPN-1 RRP VPN 001 +1 010-1 100 2.1.3 Buffer Refill Selector 13
+1-1 +1 VPN=100 VPN=101 VPN=99 VPN=102-1 VPN=100 VPN=99 VPN=101 VPN=98 RRP PTE VPN+1 VPN-1 RRP 14
3 2 2 3.1 Wide Range Support Wide Range Support WRS ±1 PTE WRS ±2 ±3 PTE WRS 3.1 WRS ±2 2WRS ±3 3WRS 3WRS 2.1 2.6 VPN±2 VPN±3 2 1 1 WRS WRS TLB WRS TLB PPTE 2.2 15
WRS WRS PTE WRS ªªª u ªªª preload preload preload +3 +2 +1 preload preload preload Last Hit PTE -1-2 -3 TLB ªªªªªªª TLBªªªªªªªª 3.1: Wide Range Support WRS 3.1.1 WRS 2.1.3 WRS 1PTE WRS PTE PTE WRS WRS PTE 3.2 16
BURST ADDRESS 2BIT OFFSET (1PTE=1WORD) Buffer Memory Address 00 ««««««««««««««««011 100 PTP + VPN = PTE Address ««««««««101 = 010 d «««««««««««««««««««««««««««««««««««««««««««110 111 000 001 ªªª ªªªªu ««««««««««««««010 3.2: WRS 17
WRS PTE 32Bit PTEA(Page Table Entry Address) PTP(Page Table Pointer) VPN 1 VPN PTE 4KB VPN 32bit 12bit =20bit 1PTE32 4byte 2 PTEA 4MB 2 1WORD (bit 8 3bit) WRS 8 4WRS 8+1=9 RRP VPN 8 ( ) RRP VPN +1 VPN+1 1 VPN+1 3 8 3 010 011 100 101 3 SDRAM 2 3.1 2 (VPN + ) (VPN ) 1 CPU 1 PTP VPN ( PTP 0 ) PTEA PTE 2 PTEA MIPSR4000 PTE PTE PTE 18
3.1: 8 2 Starting Address Addressing(Decimal) A2 A1 A0 0 0 0 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0 0 1 1, 2, 3, 4, 5, 6, 7, 0, 1, 0, 3, 2, 5, 4, 7, 6, 0 1 0 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 6, 7, 4, 5, 0 1 1 3, 4, 5, 6, 7, 0, 1, 2, 3, 2, 1, 0, 7, 6, 5, 4, 1 0 0 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 1 0 1 5, 6, 7, 0, 1, 2, 3, 4, 5, 4, 7, 6, 1, 0, 3, 2, 1 1 0 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 4, 5, 2, 3, 0, 1, 1 1 1 7, 0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0, 3.1.2 1?? VPN ± + VPN+5 VPN 2 ±4 WRS VPN±1PTE 3.3 RRP VPN Case A Case B ±1VPN RRP VPN PTEA 4WRS PTE PTE Case A 000 VPN-1 111 PTE Case B 111 VPN+1 000 PTE 8 WRS RRP VPN 1/4 RRP VPN PTEA PTE VPN+1 PTEA 19
Page Table Burst Address 110 111 Ç Ç Ç Æ Ç Ç È Æ Ç P T E «ªªª ª ª «Case A:VPN-1 Case A:RRP VPN Case A:VPN+1 Case B:VPN-1 Case B:RRP VPN Case B:VPN+1 «ªªª ª ª «PTE È PTE 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 000 001 010 011 Ç È Ç Ç Ç Ç È Ç 100 101 110 111 3.3: WRS 20
8 1/4 1/8 VPN 1 PTEA PTE 3.1.3 WRS 2WRS 3.4 CPU WRS 16byte 2WRS 32 4 WRS 3 RRP VPN Register Burst Buffer RRP 3.1.2 RRP VPN RRP WRS RRP VPN RRP WRS WRS 3.5 3.6 3.5 3.6 RRP VPN Register 1 4 (Predictor Control Unit) (Address Generator) 3 3.1.2 WRS 4 RRP PTE ( ) VPN PTE WRS PTE PTE 21
3.4: 2WRS 22
ªª ªªªªªª s ªª ªªª v ªªª ªªªª s ªªª ªªªªª ªª ªªªª ~ ªªª ªªª ªªªª ªªª ªªªªª ªª ªªª ªªª 3.5: 23
ªªªªªª ªªªªªª s ªªª ªª ª s ªªª ªªª ªªª ªª ªªª ªª s ªªªªª ªªª ªª ªªª ªªª ªªªªªª ªªªªªª ªªª ªªªªªª ªªª ªªª ªª ªªª ªªªªªª «ªªª ªªª ªªª ªª ªªª s ªªª s ªªª ªªª ªªª ªªªªª ªªª ªªª ªªª ªª ªªª ªªª ªª ªªª ªªª ªª ªªª ªªª ªª ªªª 3.6: 24
PTE Refill Selector Burst Controler Refill Selector RRP 25
3.2 Multiple Operand Support Multiple Operands Support MOS MOS 3.7 ªªª u ªªª preload preload ªªªªa ªªªªb ªªªªc +1 Last Hit PTE of a -1 +1 Last Hit PTE of b -1 +1 Last Hit PTE of c -1 ªªªªªªª TLBªªªªªªªª TLB 3.7: Multiple Operands Support MOS for(i=0;i<n;i++) a[i]=b[i]+c[i]; WRS b c a 26
5 MOS MOS 2 2MOS 3 3MOS 3.7 3MOS 3MOS 3 a b c 1 3.2.1 MOS 1. MOS 2. MOS 3MOS MOS 3. MOS 4.LRU(Least Reacently Used) ( ) 1 MOS MOS 2 MOS MOS 3 5 SPARC CPU 27
RRP VPN TLB 4 LRU 4 3 1 LRU 1 LRU 1 MOS 4 LRU 3.2.2 MOS 4MOS 3.8 MOS LP 4MOS LP0 LP3 4 1 1 VPN MOS VPN Preliminary Buffer Check Active MOS Switcher VPN Preliminary Buffer Check MOS 3.9 3.2.1 LRU LRU TLB LRU LRU LRU 4MOS 4bit 4=16bit 16bit 6 (LRU Bit Field) 4MOS nmos n 2 6 LRU (10 ) LRU LRU 2 MOS 28
3.8: 4MOS LRU LRU Controler LRU Bit Field MOS RRP ( VPN ) PTE MOS LP VPN Memory Access Request Que LP ACK LP 29
ªªª } ªªª ªª ªªª ªªªª ªªª e y ªª ª v ªªª ªª ª v ªªª ªªª ªªª ªª ªªª vƒ ªªª ªªª ªªª ªªª ªªª ªªª ªªª ªªª vƒ 3.9: MOS 30
VPN ACK MOS Control Unit ACK Memory Access Request Que MOS MOS 1 MOS MOS 3.2.2 MOS MOS MOS 3.3 WRS MOS TLB TLB TLB WRS MOS 3.3.1 TLB TLB TLB PPTE TLB TLB WRS MOS 1 4KB 1 1024 WRS ±1 2048 2048 PTE PPTE TLB WRS MOS 31
TLB WRS TLB 3.3.2 WRS MOS WRS MOS TLB PPTE WRS MOS 3.10 preload +3 +2 +1 Last Hit PTE of a -1-2 -3 +3 +2 +1 Last Hit PTE of b -1-2 -3 +3 +2 +1 Last Hit PTE of c -1-2 -3 u ªªª TLB ªªªªªªª TLBªªªªªªªª 3.10: WRS MOS 32
4 VHDL 4.1 Integer Integer Unit Unit Data Data TLB TLB Instruction Instruction TLB TLB TLB TLB Misshandler Misshandler Instruction TLB Instruction TLB Predictor Predictor Buffer Buffer Buffer Buffer Data TLB Data TLB Predictor Predictor 4.1: 3 TLB TLB 33
MMU(Memory Management Unit) TLB TLB MMU 4.1 [Integer Unit] CPU Integer Unit Integer Unit 8.1 4.2: Out-of-Order 5 32 IF(InstructionFetch) ID(Instruction Decode) EX(EXecution) MEM(MEMory access) WB(Write Back) MIPSI ID 34
EX ID TLB MMU MIPS R3000 A 4.2 MMU MMU Integer Unit MIPS MMU MIPS MIPS TLB MMU TLB MMU 4.3 4.2.1 MMU TLB MIPS TLB TLBI(TLB Index) TLBR(TLB Read) TLBW(TLB Write) TLBP(TLB Probe) 0 MTC0(Move To Coprocessor 0) MFC0(Move From Coprocessor 0) 1 MMU 0 4.1 MIPS TLB MIPS R3000 TLB 4.2 MIPS TLB MMU Reserved COP0 31 MMU and Predictor Status(MPSR) MMU and Predictor Status 4.4 MPSR 1 4 TA(TLB Active) TLB 1 0 TLB TF(TLB Flush) TLB 1 1 TLB Valid 1 MIPS CPU Integer Unit MIPS 0(COP0) 1(COP1) 35
4.3: MMU 36
4.1: 0 COP0 COP0 COP0 0 Index Reserved 1 Random Reserved 2 EntryLo0 Reserved 3 EntryLo1 Reserved 4 Context PTP Register 5 PageMask Reserved 6 Wired Reserved 8 BadVaddr Reserved 10 EntryHi Reserved 12 SR SR 13 Cause Reserved 15 PRID PRID 14 EPC Reserved 31 Reserved MMU and Predictor Status 4.2: MIPS R3000 TLB OFF & Cache ON kseg0 0xa000 0000 0xbfff ffff 0.5GB TLB OFF & Cache OFF kseg1 0x8000 0000 0x9fff ffff 0.5GB TLB ON & Cache ON kseg2 0xc000 0000 0xffff ffff 1GB kuseg 0x0000 0000 0x7fff ffff 2GB 37
MPSR 31 30 3 2 1 0 PA 000ªªªªªª ªªªªªª000 PF TF TA TA : TLB Active TF : TLB Flush PF : Predictor Flush PA : Predictor Active 4.4: MPSR 0 Valid 0 TLB TLB 2 PF(Predictor Flush) Valid 0 Valid 0 PA(Predictor Active) 1 0 TLB TLB 1 TA 1 TLB VPN PTEA Dirty TLB TLB 2 MIPS TLB ASID TLB Flush ASID 4.2.2 38
4.2.2 TLB TLB MIPS TLB MIPS R3000 TLB TLB TLB 4.5 4.5: TLB 32 4KB TLB TLB MIPS Entry Hi Entry Lo Entry Hi MIPS R3000 Entry Hi VPN ASID 0 3 TLB Entry Hi VPN ASID Entry Lo MIPS R3000 Entry Lo 3 0 TLB 32 39
PFN(Physical Flame Number) 4 Attribute 0 PFN Attribute N D V G TLB Entry Lo PPN Attribute MIPS R3000 Attribute 4.3 4.3: MIPS R3000 Attribute N D V G 1 1 Write,1 TLB 1 Entry Hi ASID MIPS TLB Attribute TLB PTE MIPS Attribute TLB MMU TLB 4 PPN(Physical Page Number) MIPS R6000 PPN 40
TLB 4.6 ª 4.6: TLB TLB VPN PPN Attribute 2.2.1 LRU LRU Dirty Valid TLB LRU 1 LRU 4KB VPN PPN 20 32 Dirty 41
5 VHDL C 5.1 TLB 2.2 Synopsys FPGA Compiler II Xilinx FPGA VIRTEX2 2V6000FF1152 ( ) 20MHz Primitive reference count FPGA LUT(LookUp Table) LSI Timing Path Groups Clocks 5.2 Model Technology ModelSim C TLB TLB / MMU TLB MIPS TLB TLB 42
1 5.2.1 5.1 #define PAGE_SIZE 1024 /* 4KB/4 */ #define NUM_OF_TLB_MISS 5 int test_data[ PAGE_SIZE*NUM_OF_TLB_MISS ]; int dataset_access(); int main( void ){ register int a; a = dataset_access(); } int dataset_access(){ int i,sum; for ( i=0;i<page_size*num_of_tlb_miss;i++) test_data[ i ] = i; for ( i=0;i<page_size*num_of_tlb_miss;i++) sum += test_data[ i ]; } return sum; 5.1: 1 43
6 6.1.1 6.1.2 6.1 MMU 1WRS-1MOS 1WRS-4MOS 2WRS-1MOS CPU 1WRS-1MOS CPU 1WRS-4MOS CPU 2WRS-1MOS CPU CPU MMU 1WRS-1MOS CPU MMU 1WRS-1MOS 1WRS-4MOS CPU MMU 1WRS-1MOS 1WRS-4MOS 2WRS-1MOS CPU MMU 1WRS-1MOS 2WRS-1MOS 6.1.1 6.1 (PIPELINE) MMU (MMU) 1WRS-1MOS (1WRS-1MOS) 1WRS-4MOS (1WRS-4MOS) 2WRS-1MOS (2WRS-1MOS) 44
6.1: FDE FD LUT XORCY TLB MUX CMP PIPELINE 1502 0 3765 16 0 0 0 MMU 2723 0 2411 8 0 1 0 1WRS-1MOS 160 7 330 4 0 0 0 1WRS-4MOS 740 40 1736 0 0 0 0 2WRS-1MOS 213 0 246 2 0 0 1 Normal CPU 4224 0 6087 23 0 0 0 1WRS-1MOS CPU 4718 16 7661 27 0 0 0 1WRS-4MOS CPU 2610 45 5998 23 2 0 0 1WRS-4MOS CPU 5298 45 9100 23 0 0 0 2WRS-1MOS CPU 4795 10 7658 25 0 0 0 CPU(Normal CPU) 1WRS-1MOS CPU(1WRS-1MOS CPU) 1WRS-4MOS CPU(1WRS-4MOS CPU) 2WRS-1MOS CPU(2WRS-1MOS CPU) 6.1 FDE D FD D LUT XORCY XOR TLB MUX CMP FPGA MUX CMP LUT CPU TLB TLB LUT FDE 1TLB FDE 1344 LUT 1551 TLB 1WRS-4MOS CPU 1WRS-4MOS CPU FDE LUT 2 FDE FD LUT XORCY 1WRS-4MOS CPU Normal CPU 1WRS-1MOS 3.5% 1WRS-4MOS 17.5% 2WRS-1MOS 5.0% 1WRS-1MOS 5.5% 1WRS-4MOS 28.5% 2WRS-1MOS 4.0% MOS 45
50% 80% FPU Normal CPU CPU TLB- CPU Normal CPU 1WRS-1MOS CPU 11.5% 1WRS-4MOS CPU 24.5% 2WRS-1MOS CPU 13.5% 1WRS-1MOS CPU 25.85% 1WRS-4MOS CPU 49.4% 2WRS-1MOS CPU 25.8% 6.1.2 6.2 6.2: In- RC(ns) RC- Out(ns) RC- RC(ns) (MHz) PIPELINE 2.57 2.77 11.67 85.69 MMU 5.21 6.02 5.78 166.11 1WRS-1MOS 4.77 4.70 5.34 187.27 1WRS-4MOS 4.77 3.65 5.34 187.27 2WRS-1MOS 3.10 3.82 3.58 261.78 Normal CPU 3.89 11.30 11.67 85.69 1WRS-1MOS CPU 4.77 10.86 11.67 85.69 1WRS-4MOS CPU 4.20 10.86 11.67 85.69 2WRS-1MOS CPU 5.21 10.86 11.67 85.69 6.1.2 In- RC(ns) RC- Out(ns) RC- RC(ns) 3 PIPELINE 11.67ns CPU Normal CPU 1WRS-1MOS CPU 1WRS-4MOS CPU 2WRS-1MOS CPU 85.69MHz PIPELINE PIPELINE In- RC RC- Out RC- Out TLB Normal CPU 1WRS-1MOS CPU 1WRS-4MOS CPU 2WRS-1MOS CPU VPN 46
FPGA / FPGA Compiler 6.2 47
7 48
8 MMU TLB TLB TLB MMU TLB 49
A 50
8.1: 51
Synopsys Model Technology University Program 52
[1] Ashley Saulsbury, Fredrik Dahigren and Per Stenstrom: Recency-Based TLB Preloading Proceedings of the 27th annual international symposium on Computer architecture, Pages 117127,2000 [2] M.Talluri, S.Kong, M.D.Hill and D.A.Patterson: Tradeoffs in Supporing Two Page Sizes Proc of ISCA, pages 415424, 1992 [3] Madhusudhan Talluri and Mark D.Hill Surpassing the TLB Performance of Superpages with Less Operating System Support In Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 171182, 1994. [4] J. E. Smith, A Atudy of Branch Prediction Strategies, Proc of ISCA, pp.135148, May, 1981 53