Slide 1

lts1III PENDEKATAN ALGORITMISPERANCANGAN SISTEM DIGITALIII.3 Register Transfer Level III.3.1 Struktur dan elemen RTL (datapath & controller) III.3.2 Operasi & Notasi RTLIII.3.3 Sintesis datapath & controllerIII.3.3 Sintesis Datapath & Controllerlts3Deskripsi masalahIdentifikasi :1. Data/Register2. Operasi operasi mikro 3. Kondisi atau syarat-syaratnya.4. Aliran datanyaAlgoritma (program RTL)Sintesis Datapath lts41. Data (input, internal, output) : Register register (storage)2. Operasi operasi mikro : Operator operator3. Kondisi atau syarat-syaratnya : Pembangkit kondisi4. Aliran datanya : Interkoneksi elemen datapath, saklar-saklar, titik- titik kendali.Identifikasi kebutuhan :

Kondisi Datapathx

Contoh 1 : Rancanglah bagian datapath untuk komputasi , berdasarkan algoritma deret Taylor.

term0 term1 term2 term3 term4iterasi 1iterasi 2iterasi 3iterasi 4misalkan s/d n = 4wait : if start goto wait ; x in ; //baca input x term 0, n 0 , y 0 ; //inisialisasi term incr(term) ; loop : term mul(term, x); //hitung suku ke n y add(y, term), n incr(n) ; //hitung if n < 4 goto loop, else out y ; goto wait ;

Dari algoritma diturunkan program RTL :Dari program RTL dapat diidentifikasikan komponen-komponen storage, operator, titik-titik kendali, kondisi-kondisi dan interkoneksi dalam datapath.xldldxinx in Register x (register input) :term mul(term, x)Register y (register output) :y 0 y add(y, term), yldldxclrx oexclr oeoutout yRegister-register, & titik-titik kendali yg dibutuhkan pada register-register tsb :in

xytermldldtermclrterm incrtermclr inr Register term :term 0, term incr(term) term mul(term, x)y add(y, term), n 0 kendali clrif n < 4 kondisin incr(n) kendali incr Register n :nclrterm incrtermclr inrn = 4Q0Q1Q2n = 4term mul(term, x)y add(y, term), n incr(n)term incr(term) Operator-operator :multermxtermaddtermyyoperasi incr built-in dalam register n dan termDari identifikasi register & operator dapat ditentukan interkoneksinya,misalkan(a) Interkoneksi titik-ke-titik :ldldxxinyldldxclrx oexclr oeouttermldldtermclrterm incrtermclr inrnclrterm incrtermclr inrn = 4multermxtermaddtermyy Interkoneksititik-ke-titikldldxxinyldldxclrx oexclr oeouttermldldtermclrterm incrtermclr incrnclrterm incrtermclr incrn = 4multermaddtermyyke controllerdari controller(b) Interkoneksi Bus :Untuk interkoneksi Bus, harus dijamin selektifitas komponen sumber dan komponen tujuan.- Semua komponen yang outputnya terhubung ke bus haruslah bertipe 3-state atau memiliki kendali output-enable.- Semua komponen yang inputnya terhubung ke bus haruslah memiliki kendali load atau input-enable.ldldx x inldbusldldy y outldbusRegister :ldldterm term

ldbus clr incrclrterm incrtermldldnn ldclr incrclrn incrnn = 4Register n tidak terhubung ke busOperator :Untuk selektifitas input operator, dibutuhkan dua register yang terhubung ke bus untuk masing-masing operator. mul R1R2ld ld ldR1 ldR1 busadd R3R4ld ld ldR1 ldR1 busDengan ARG sebagai input, hitung 1/ARG sampai dengan error tertentu.

Melalui pendekatan Newton Raphson , x = 1/ARG dipandang sebagai akar dari persamaan f(x) = 0 dimana f(x) = ARG 1/x, dan f(x) = 1/x2.Dengan demikian, x = 1/ARG dapat dihitung menggunakan algoritma iteratif Newton Raphson xn+1 = xn- f(xn)/f(xn)Dengan f(xn) = ARG - 1/xn dan f(xn) = 1/xn2

makaxn+1 = xn (ARG 1/xn)/(1/xn2) = xn - xn2 (ARG - 1/xn) = (2xn ARG.xn2 )Contoh 2 : Algoritma Newton-Raphson untuk menghitung nilai 1/ARGatau xn+1 = (2 ARG.xn ) xn ,

dengan error = |xn+1 xn | tertentu.Bila ARG disimpan di register ARG, error disimpan di register ERR, dan xn disimpan di register REC,

maka algoritma level tinggi untuk komputasi tersebut adalah

ARG dan eror sebagai inputlts18Algoritma level tinggi : RECIP: { inputs ARG, ERR type fraction, start type boolean ; outputs REC type fraction, done type boolean } WAIT: done 1 || WAIT if start ;COMPUTE: REC 1 || done 0 ; until ( |ARG.REC 1 | < ERR/2) do REC ( 2 ARG.REC) . REC ; WAIT ;End RECIP

- Bentuk until diterjemahkan ke level implementasi.looplts19until ( |ARG.REC 1 | < ERR/2) do REC ( 2 ARG.REC) . REC ;Bentuk level tinggi :Bentuk level rendah :/* hitung ARG.REC *//* hitung ERR/2 *//* hitung (2 - ARG.REC) *//* hitung (2 - ARG.REC).REC *//* bandingkan (ARG.REC -1) dengan (ERR/2) *//* hitung (ARG.REC 1) */loop: x MUL(ARG,REC);y SUB(2,x); z MUL(y,REC); w DIV(ERR,2) ;DECR(x);COMP(x,w); loop if LESS ;/* iterasi berikutnya bila syarat tidak dipenuhi*/REC z/* simpan harga REC yang baru */lts20Operasi operasi yang dapat diparalelkanloop: x MUL(ARG,REC);y SUB(2,x)z MUL(y,REC) ||wDIV(ERR,2) ;||DECR(x) ;COMP(x,w) loop if LESS ;||REC z||lts21Algoritma Level ImplementasiRECIP: { inputs ARG[16], ERR[16] type fraction, start type boolean ; outputs REC type fraction, done type boolean; local_obyects x,y type integer } WAIT: done 1 || WAIT if start ;COMPUTE: REC 1 || done 0 ;loop x MUL(ARG,REC) ; y SUB(2,x) || wDIV(ERR,2) || z MUL(y,REC); REC z || DECR(x); COMP(x,w) || loop if LESS; WAIT ;End RECIP(diasumsikan untuk data 16 bit)lts22 Operasidone 1REC 1 done 0x MUL(ARG,REC) y SUB(2,x) wDIV(ERR,2) z MUL(y,REC)REC z DECR(x)COMP(x,w) OPERASI OPERASI MIKRO KONDISI KONDISIkondisistart*LESSx < wlts23multsubdivmux2xyRECARGERRdemuxxzywcompxwLESS Transfer Registerlts24multsubdivmux2xyRECARGERRdemuxwzcompLESS0 10 1lts25multsubdivmux2xyRECARGERRdemuxwzcompLESS0 10 1ldxldyldRECldwselbselaldzlts26Contoh 3 : Sebuah sistem komputasi dengan input m dan n , output z, untuk menghitung fungsi

4 (m + |n| ) / 2 untuk m < |n|z = 4m untuk harga m > |n| Rancanglah sistem tersebut tanpa menggunakan adder. Algoritma untuk sistem tsb : mnzstartpembulatan keataslts27iterasiyxy+1x-1z = 4y145yx--4x5=20iterasiyxy+1x-1z = 4y125y xk1compa-ratork2xysign-bitRegister xVariabel kondisi : implementasi pembangkit kondisi x < 0 y < x lts32Identifikasi Interkoneksi , Saklar & Titik Kendali. Operasi mikrox n X LOAD(n)x -x X CS(X)x x-1 X DEC(X)y m Y LOAD(m)y y + 1 Y INC(Y)z 2 y Z SHL(Z)Z y Z YXCSYZnDECsaklarINCmSHLsaklarsaklarYOperator CS, DEC, INC, SHL dapat dieliminasi bila register-registernya memilikimode CS, DEC, INC atau SHL.selectselectselectloadloadloadlts33 Y

X

Z

INCDECCSCOMPC2 C3C4mnyxk1k2zC1MUXMUXIdentifikasi interkoneksi&Titik-titik KendaliC5C6lts34 Y

X

Z

INCDECCSCOMPC2 C3C4mnyxk1k2zC1MUXMUX Bagian Kendali

C1C2C3C4C5endstartclockDataSinyal kendaliKondisiDatapathC6C5Rancanglah bagian datapath untuk penjumlahan komplemen-2 dari integer X0, X1, .. 8-bit yang tersimpan dalam register-array. Penjumlahan dihentikan ketika dijumpai XN = 0, atau bila terjadi overflow.Asumsi : X0, X1, sudah ada didalam register array. addressRegisterArraydata RdWr88datapath?controller??startdonesumoverflowSoal 1 :Untuk Algoritma komputasi harga cos x dibawah ini,

(a) Tuliskan program RTL untuk komputasi diatas, sampai dengan suku ke 4 saja. (b) Gambarkanlah Datapathnya disertai penjelasannya. (c) Gambarkan Diagram Keadaan bagian kendalinya disertai penjelasannya.cos(x) = 1 - + - + - + . . . x22!x44!x66!x88!x1010!Soal 2 :

Soal 3 :Dengan algoritma deret Taylor untuk komputasi harga cos x dibawah ini, (a) Tuliskan program RTL untuk komputasi diatas, sampai dengan suku ke 4 saja. (b) Gambarkanlah Datapathnya disertai penjelasannya.(c) Gambarkan Diagram Keadaan bagian kendalinya disertai penjelasannya.

Pengendaliprogram RTLDatapathlts39 Transformasi algoritma RTL ke Diagram Keadaan FSM 1 statement RTL 1 keadaan FSM peruntunan statement peruntunan keadaan Sinyal sinyal kendali yang harus diaktifkan pada tiap statement RTL = output yang harus dibangkitkan pada tiap keadaan FSM. Implementasikan bagian pengendali mesin komputasi berdasarkan diagram keadaan FSM tersebut.Sintesis Controlpath(transisi keadaan)lts40 RECIP: {Inputs ARG, ERR type bit-vector, start type boolean; Outputs REC type bit-vector, done type boolean; Local-objects A,E, W, Y type bit- vector, k type boolean } Wait : done 1 || Wait if start ;Compute: A ARG || REC 1 || E ERR/2 || done 0 ; Loop: W MUL(A, REC) ; Y SUB(2, W) ; REC MUL(Y, REC) || k = COMP(E,SUB(W,1)) Loop if k | Wait if k ;end RECIPdeklarasi dataFSM 1 bila |W-1| > E k = 0 untuk harga lainnyalts41ARECEmux1 0c4multwsubsubycomp16161616161616161616161616ARGERR/2c1c6c7c5c2c3donec8c9kdone112RECSinyal sinyalkendali :c1: A ARGc2: REC 1c3: REC MUL(Y,REC)c4: selectc5: E ERR/2c6: W MUL(A,REC)c7: Y SUB(2,W)c9: done 0c8: done 1Datapathlts Wait : done 1 || goto Wait if start ;Compute: A ARG || REC 1 || E ERR/2 || done 0 ; Loop: W MUL(A, REC) ; Y SUB(2, W) ; REC MUL(Y, REC) || goto Loop if k else goto Wait if k ;end RECIPdeklarasi datac8c1c2c5c9c6 , c4c7c3 , c4S0S1S4S3S2startS0/ S1/S2/S3/S4/kstartkc8c1,c2,c5,c9c7c6 , c4c3 , c4FSM bagian kendaliRECIP:43Pengendalistartkc1c3c2c9DatapathARGERR/2RECdoneclockS0S1S4S3S2startS0/ S1/S2/S3/S4/kstartkc8c1,c2,c5,c9c7c6 , c4c3 , c4lts44( Penyandian sederhana S0=000 ; S1=001 ; S2=010 ; S3=011 ; S4=100 )Tabel Keadaan Biner PengendaliS(t)x(t)E(t) = S(t+1)output(t)Q2Q1Q0startkD2D1D0c1c2c3c4c5c6c7c8c90000d0000000000101d001000000010001dd010110010001010dd011000001000011dd100000000100100d0010001100000d1000001100000101dd110dd111ddkode yg tidak terpakailts45Dari Tabel Keadaan FSM : Fungsi Eksitasi D0 = ..... D1 = ..... D2 = ..... Fungsi output c1 = ..... c2 = ..... c3 = ..... c4 = ..... c5 = ..... c6 = ..... c7 = ..... c8 = ..... c9 = .....Rangkaian kombinatorialstartkc1c3c2c9Q0 clk D0 Q1 clk D1 Q2 clk D2Kendali Hardwired (Random Logic)clockF(start, k , Q2 , Q1 , Q0 )Address decoder012345:3031Q0 D0

clkQ1 D1

clkclockKondisi &Ext.inPresent StateeksitasiKendali(ke datapath)alamatROMImplementasi bag. kombinatorialmenggunakan ROMD0 D1 D2 c9 c8 c2 c2 c1kstartQ2 D2

clkmenjadi dasar kendali terpogram mikro.lts47Ragam implementasi bagian KendaliFixed : HardwiredProgrammable : MicroprogrammedKendali hardwired : Bagian kombinatorial diimplementasikan menggunakan gerbang-gerbang logika (random logic). Modifikasi skenario pengendalian harus mengubah struktur perangkat-kerasnya. Kecepatan tinggi.

Kendali terprogrammikro : bagian kombinatorialnya diimplementasikan menggunakan ROM dan sequencer untuk peruntunan alamat ROM yang akan dibaca. Modifikasi skenario pengendalian dilakukan dengan hanya mengubah (memprogram ulang) isi ROM (fleksibel).ltsHardwiredMicroprogrammed Sequencer ROMalamat ROMext.input & kondisisinyalkendaliRangkaian gerbang logikastateeksitasisinyalkendaliext.input & kondisiPengingat keadaanNext-addressinformationNext-addressgeneratorControl addressregisterAddress

ControlMemory(ROM)

Control addresssequencerext. control in.kondisiNext-addressinformationSinyal kendaliruntun eksekusi instruksi assemblyLoad M(25H)100100101010110111100101aa+1a+2a+5a+3a+4mIamIa+1mIa+5mIa : instruksi mikro di alamat a.Program mikro load M(25H)