RANDY MANDALA
2008470095
ARSITEKTUR KOMPUTER
Pendahuluan
Setiap hal yang dikerjakan CPU dibagi-bagi menjadi beberapa langkah yang sederhana dan berurutan. Osilator clock membangkitkan clock CPU yang digunakan dalam langkah (step) kerja CPU dalam urutan perkerjaannya. Karena clock CPU ini sangat cepat untuk ukuran manusia, sehingga yang terlihat bahwa CPU bekerja secara langsung dan cepat.
Mikrokontroler 8-bit dari Motorola M68HC05 dan M68HC11 memiliki organisasi khusus yan disebut dengan arsitektur Von Neumann. Dalam arsitektur ini, CPU dan rangkaian memori di-interkoneksi-kan dengan bus alamat dan bus data. Bus alamat digunakan untuk menentukan lokasi memori yang mana yang akan diakses, dan bus data digunakan untuk mengirim informasi baik dari CPU ke lokasi memori dan sebaliknya.
Dalam arsitektur implementasi Motorola ini terdapat beberapa memori spesial yang disebut dengan register CPU yang terletak di dalam CPU itu sendiri. Register ini mirip dengan memori yang dapat menyimpan informasi. Tetapi register ini terjalur langsung di dalam CPU dan bukan bagian dari memori konvensional mikrokontroler.
CPU menganggap semua lokasi memori sebagai satu kesatuan walaupun di dalamnya terdapat instruksi program, data variabel, maupun kontrol input-output (I/O). Teknik semacam ini yang disebut dengan memory-mapped I/O. Artinya, semua piranti input-output dari sistem mikrokontroler memiliki alamat tersendiri yang ikut dipetakan dalam peta memori, sehingga dianggap sebagai bagian dari memori itu sendiri.
Di dalam CPU juga terdapat komponen ALU atau Arithmatic Logic Unit yang digunakan untuk melakukan kalkulasi aritmatika dan logika yang didefinisikan oleh instruksi. Berbagai macam variasi operasi aritmatika biner dikerjakan dalam ALU ini. Hampir semua operasi aritmatika biner didasarkan pada operasi tambah. Pengurangan dikerjakan sebagai proses tambah dengan salah satu data dikomplemenkan. Perkalian dikerjakan sebagai urutan beberapa proses tambah dan operasi shift dalam ALU. Blok diagram dari CPU M68HC05 ditampilkan dalam gambar 4.1 di bawah ini.
CPU yang berbeda memiliki set register yang berbeda pula. Perbedaan utama terletak pada jumlah dan ukuran dari register itu sendiri. Dalam gambar 4.1 diperlihatkan register-register CPU yang terdapat dalam mikrokontroler keluarga M68HC05.
Register A berukuran 8 bit, juga dikenal sebagai akumulator karena register ini digunakan untuk menyimpan hasil dari operasi aritmatika dan manipulasi data. Register ini juga dapat langsung diakses untuk operasi non-aritmatika. Akumulator digunakan dalam proses eksekusi dari program saat isi dari beberapa lokasi memori yang digunakan di-load ke akumulator. Demikian juga instruksi penyimpanan akan menyebabkan isi dari akumulator disimpan dalam memori yang telah ditentukan.
Register X adalah index register yang berukuran 8 bit. Kegunaan utama dari index register ini adalah untuk menunjukkan suatu area memori di mana CPU akan mengambil atau menuliskan suatu informasi. Kadang-kadang index register juga disebut dengan pointer register.
PC atau program counter digunakan CPU untuk menata urutan alamat instruksi yang akan dikerjakan. Saat CPU reset atau baru dihidupkan, PC ini dimuati dengan alamat yang telah ditentukan dalam reset vector. Lokasi reset vector ini berisi alamat dari instruksi pertama yang akan dikerjakan oleh CPU. Saat suatu instruksi dikerjakan, CPU akan menambah isi PC sehingga akan menunjuk ke alamat informasi berikutnya yang akan dibutuhkan CPU. Jumlah bit dari PC sama persis dengan jumlah jalur bus alamat. Isi dari register ini dinyatakan dalam empat digit heksadesimal di mana enam bit teratas selalu nol karena hanya 10 bit jalur bus alamat.
CCR atau condition code register adalah register dengan ukuran 8 bit, yang menyimpan indikator status dari hasil operasi CPU sebelumnya. Terdapat tiga bit teratas tidak digunakan dan selalu sama dengan logika satu. Instruksi percabangan menggunakan bit-bit status dalam register ini untuk mengerjakan suatu keputusan percabangan.
Isi dari CCR ini adalah sebuah interrupt mask dan empat indikator status seperti pada gambar 4.1. Kelima flag tersebut adalah H atau half cary
Bit I (interrupt mask) bukanlah status flag tetapi merupakan bit yang akan men-nonaktif-kan semua sumber interrupt yang maskable saat bit ini diset. Interrupt baru akan aktif jika bit ini nol. Jika ada interrupt eksternal yang terjadi saat bit I diset, maka interrupt tersebut akan di-latch dan akan diproses saat bit I dinolkan. Karena itu, interrupt yang terjadi tidak akan hilang. Setelah interrupt ditangani, instruksi RTI (return from interrupt) akan menyebabkan register ini dikembalikan ke nilai semula. Umumnya, bit I ini akan menjadi nol setelah instruksi RTI dilaksanakan.
Flag N (negative) akan diset jika hasil dari operasi aritmatika, logika, maupun manipulasi data yang terakhir adalah negatif. Nilai negatif dalam two's complement ditandai jika bit MSB adalah satu. Flag Z (zero) diset jika hasil dari operasi aritmatika, logika, maupun manipulasi data terakhir adalah nol. Instruksi perbandingan (compare) akan mengurangi suatu harga dari suatu lokasi memori yang akan dites. Jika nilainya sama, maka bit Z ini akan diset.
Flag C (carry/borrow) digunakan untuk menandai apakah ada carry dari hasil operasi tambah atau ada borrow darioperasi pengurangan. Instruksi shift dan rotate juga dapat memakai bit C ini.
SP atau stack pointer digunakan sebagai pointer ke lokasi yang tersedia berikutnya dalam tumpukan stack dalam uruatn LIFO (last-in first-out). Stack ini dapat dianalogikan sebagai tumpukan kartu. Setiap kartu menyimpan satu byte (8 bit) informasi. Dalam suatu saat, CPU dapat menaruh satu kartu di atas tumpukan kartu tersebut maupun mengambil satu kartu dari tumpukan. Kartu di dalam tumpukan tidak dapat diambil kecuali jika kartu di atasnya sudah diambil sebelumnya. Stack mirip dengan tumpukan kartu ini hanya saja dalam fisiknya, stack mempunyai arah tumpukan ke bawah bukan ke atas seperti pada tumpukan kartu.
SP akan menunjuk pada alamat stack yang akan tersedia berikutnya. Jika CPU menaruh informasi dalam stack, maka data tersebut akan dituliskan dalam memori yang ditunjukkan oleh nilai SP saat itu, dan kemudian nilai SP akan dikurangi satu sehingga SP akan menunjukkan ke lokasi memori berikutnya yang kosong untuk digunakan sebagai penyimpan berikutnya. Jika CPU mengambil data dari stack, SP akan ditambah satu sehingga menunjukkan ke lokasi stack yang terakhir, dan kemudian data diambil dan dibaca oleh CPU. Saat CPU pertama kali dihidupkan atau setelah instruksi Reset Stack Pointer (RSP), maka SP akan menunjukkan memori tertentu dalam RAM.
Reset digunakan untuk memaksa sistem mikrokontroler untuk menuju alamat tertentu. Sistem periperal dan sejumlah bit kontrol dan status juga dipaksa untuk menuju ke state awal sebagai hasil dari proses reset. Aksi-aksi berikut ini yang terjadi akibat proses reset dari mikrokontroler:
1. Semua register data direction (DDR) diset nol (input)
2. Nilai SP dipaksa menjadi $00FF
3. Bit I dalam CCR diset
4. Latch interrupt eksternal dinolkan
5. Latch STOP dinolkan
6. Latch WAIT dinolkan
Kondisi-kondisi berikut ini yang akan menyebabkan mikrokontroler M68HC05 menjadi reset:
1. Sinyal input low pada kaki RESET
2. Reset karena pertama kali dihidupkan
3. Timer watchdog COP (computer operating properly) sudah habis
4. Usaha untuk menjalankan perintah dari suatu alamat yang tidak diperbolehkan
TOKOH IT.EDSGER DIJTRA
Pada tahun 1956, Dijkstra mengembangkan algoritma untuk mencari rute terpendek antara dua titik (shortest path algorithm) yang kemudian dikenal dengan Algoritma Dijkstra.
Dijkstra menyelesaikan candidaats examen pada bidang matematika dan fisika pada tahun 1951 di University of Leyden. Pada tahun 1956 ia menyelesaikan doctoral examen pada bidang fisika teori pada universitas yang sama. Pada tahun 1959 ia mendapatkan gelar doktor dari University of Amsterdam.
Pada awal 1960-an Dijkstra menggunakan ide mutual exclusion untuk komunikasi antara komputer dan keyboard. Pada tahun 1964 ide tersebut diadopsi pada sebagian besar prosesor dan memory setelah IBM merilis arsitektur prosesor 360.
Pada tahun 1962 ia menjadi profesor matematika di Eindhoven University of Technology, kemudian pada tahun 1973 ia bekerja di Burroughs Corporation sebagai peneliti. Dijkstra meninggalkan Belanda pada tahun 1984 untuk menjadi Schlumberger Centenial Chair pada Department of Computer Sciences, University of Texas di Austin.
Dijkstra banyak mendapatkan penghargaan atas karya-karyanya. Penghargaan tersebut diantaranya adalah ACM Turing Award, Foreign Honorary Member dari American Academyof Arts and Sciences, juga penghargaan Distinguished Fellow dari British Computer Society.
Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) atau graf tak berarah (undirected graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak negatif sehingga diasumsikan bahwa k(vij) >= 0 untuk semua edges (vij) ∈ E. Algoritma dijkstra ditemukan oleh E.W Dijkstra salah seorang kontributor utama dalam pengembangan ALGOL, sebuah bahasa pemrogaman tingkat tinggi. Dan juga merupakan salah seorang pengembang dari ilmu dan dari bahasa pemrograman secara umum. E.W Dijkstra adalah lulusan dari The Gymnasium Erasmianum di Rotterdam, dan mendapatkan gelar dalam bidang matematika dan fisika teori dari universitas Leyden, dan gelar Ph.D. dalam ilmu komputer dari universitas Amsterdam. E.W Dijkstra bekerja sebagai programmer di pusat matematika, Amsterdam pada tahun 1952 sampai denga tahun 1962. Pada tahun 1962 hingga tahun 1984, E.W Dijkstra menjadi professor matematika di Universitas Teknik Eindhoven. E.W Dijkstra mengadakan Schlumberger Centennial Chair in Computing Sciences di Universitas Texas pada tahun 1984 sampai dengan tahun 1999, dan mundur dengan menyandang gelar sebagai professor kehormatan pada tahun 1999. Dengan algoritma dijkstra dapat menyelesaikan lintasan/rute terpendek dari sebuah verteks asal dan verteks tujuan dalam suatu graf berbobot G=(V,E). Jarak terpendek diperoleh dari dua buah verteks jika total bobot dari semua edges dalam jaringan graf adalah yang paling minimal. Berikut adalah langkah-langkah pencarian lintasan terpendek dengan
menggunakan algoritma dijkstra:
1. Graf yang dibuat direpresentasikan dalam matriks K=[vij]
vij = bobot sisi (i,j).
vii = 0
vij = ∞, bila tidak ada lintasan dari simpul vi ke simpul vj.
2. Dibuat tabel S = [si]
si = 1, jika simpul i termasuk lintasan terpendek.
si = 0, jika simpul i tidak termasuk lintasan terpendek.
3. Dibuat tabel D = [di] yaiu jarak dari simpul awal ke simpul awal ke simpul awal
ke simpul tujuan.
function Dijkstra(G, k, s) //deklarasi fungsi dijkstra
for each vertex v in V[G] // inisialisasi semua bobot verteks pada graf G
d[vj] := infinity // bobot vertek ke j di simpan pada array tak terhingga
previous[vj] := undefined // bobot verteks ke j sebelumnya tidak di ketahui
d[s] := 0 // set 0 pada array untuk simpul s tidak termasuk lintasan terpendek
S := empty set // set variabel S = 0
Q := V[G] // ser variabel Q dengan bobot verteks pada graf G
while Q is not an empty set // inisialisasi variabel Q
vi := Extract_Min(Q) // set bobot verteks ke i
S := S union { vi } // set variabel S
for each edge (vi,vj) // inisialisasi setiap edge pada graf
if d[vi] + k(vi,vj) < d[vj]
d[vj] := d[vi] + k(vi, vj)
previous[vj] := vi
Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem). Di bawah ini merupakan penerapan algoritma dijkstra pada graf yang mempunyai 11 vertices dengan bobot masing-masing yang mewakili jarak antar verteks. Vertices pada graf dapat mewakili suatu tempat atau ring road pada suatu wilayah geografis.
Dalam penentuan jalur terpendek pada graf di atas di butuhkan titik awal dan titik tujuan. Misalkan titik awal D dengan titik tujuan F dengan diagram pohon kita dapat mengetahui jalur mana yang dapat dilalui, dengan ketentuan jalur jalan yang telah dilalui dengan rute yang sama tidak boleh dilalui lagi dan jika telah sampai pada titik tujuan maka pencarian pada rute tersebut berhenti dan melanjutkan dengan rute lain, jika semua rute telah dilalui kita dapat mengambil kesimpulan rute mana yang akan dilalui dengan jarak yang optimum atau terpendek.
Dari diagram pohon tersebut dapat ditentukan rute yang berhasil mencapai tujuan dari vertices D ke vertices F yaitu :
D ⇨A ⇨ B ⇨F dengan total jarak = 10
D ⇨A ⇨ G ⇨ B⇨ F dengan total jarak = 18
D ⇨C ⇨ B ⇨F dengan total jarak = 13
D ⇨E ⇨F dengan total jarak = 9
Dari hasil tersebut jarak terpendek adalah D ⇨E ⇨F dengan total jarak 9. Dalam penerapan algoritma dijkstra pada graf di atas merupakan graf tidak berarah, tetapi algoritma Dijkstra dapat juga diterapkan pada graf berarah
Dijkstra menyelesaikan candidaats examen pada bidang matematika dan fisika pada tahun 1951 di University of Leyden. Pada tahun 1956 ia menyelesaikan doctoral examen pada bidang fisika teori pada universitas yang sama. Pada tahun 1959 ia mendapatkan gelar doktor dari University of Amsterdam.
Pada awal 1960-an Dijkstra menggunakan ide mutual exclusion untuk komunikasi antara komputer dan keyboard. Pada tahun 1964 ide tersebut diadopsi pada sebagian besar prosesor dan memory setelah IBM merilis arsitektur prosesor 360.
Pada tahun 1962 ia menjadi profesor matematika di Eindhoven University of Technology, kemudian pada tahun 1973 ia bekerja di Burroughs Corporation sebagai peneliti. Dijkstra meninggalkan Belanda pada tahun 1984 untuk menjadi Schlumberger Centenial Chair pada Department of Computer Sciences, University of Texas di Austin.
Dijkstra banyak mendapatkan penghargaan atas karya-karyanya. Penghargaan tersebut diantaranya adalah ACM Turing Award, Foreign Honorary Member dari American Academyof Arts and Sciences, juga penghargaan Distinguished Fellow dari British Computer Society.
Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) atau graf tak berarah (undirected graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak negatif sehingga diasumsikan bahwa k(vij) >= 0 untuk semua edges (vij) ∈ E. Algoritma dijkstra ditemukan oleh E.W Dijkstra salah seorang kontributor utama dalam pengembangan ALGOL, sebuah bahasa pemrogaman tingkat tinggi. Dan juga merupakan salah seorang pengembang dari ilmu dan dari bahasa pemrograman secara umum. E.W Dijkstra adalah lulusan dari The Gymnasium Erasmianum di Rotterdam, dan mendapatkan gelar dalam bidang matematika dan fisika teori dari universitas Leyden, dan gelar Ph.D. dalam ilmu komputer dari universitas Amsterdam. E.W Dijkstra bekerja sebagai programmer di pusat matematika, Amsterdam pada tahun 1952 sampai denga tahun 1962. Pada tahun 1962 hingga tahun 1984, E.W Dijkstra menjadi professor matematika di Universitas Teknik Eindhoven. E.W Dijkstra mengadakan Schlumberger Centennial Chair in Computing Sciences di Universitas Texas pada tahun 1984 sampai dengan tahun 1999, dan mundur dengan menyandang gelar sebagai professor kehormatan pada tahun 1999. Dengan algoritma dijkstra dapat menyelesaikan lintasan/rute terpendek dari sebuah verteks asal dan verteks tujuan dalam suatu graf berbobot G=(V,E). Jarak terpendek diperoleh dari dua buah verteks jika total bobot dari semua edges dalam jaringan graf adalah yang paling minimal. Berikut adalah langkah-langkah pencarian lintasan terpendek dengan
menggunakan algoritma dijkstra:
1. Graf yang dibuat direpresentasikan dalam matriks K=[vij]
vij = bobot sisi (i,j).
vii = 0
vij = ∞, bila tidak ada lintasan dari simpul vi ke simpul vj.
2. Dibuat tabel S = [si]
si = 1, jika simpul i termasuk lintasan terpendek.
si = 0, jika simpul i tidak termasuk lintasan terpendek.
3. Dibuat tabel D = [di] yaiu jarak dari simpul awal ke simpul awal ke simpul awal
ke simpul tujuan.
function Dijkstra(G, k, s) //deklarasi fungsi dijkstra
for each vertex v in V[G] // inisialisasi semua bobot verteks pada graf G
d[vj] := infinity // bobot vertek ke j di simpan pada array tak terhingga
previous[vj] := undefined // bobot verteks ke j sebelumnya tidak di ketahui
d[s] := 0 // set 0 pada array untuk simpul s tidak termasuk lintasan terpendek
S := empty set // set variabel S = 0
Q := V[G] // ser variabel Q dengan bobot verteks pada graf G
while Q is not an empty set // inisialisasi variabel Q
vi := Extract_Min(Q) // set bobot verteks ke i
S := S union { vi } // set variabel S
for each edge (vi,vj) // inisialisasi setiap edge pada graf
if d[vi] + k(vi,vj) < d[vj]
d[vj] := d[vi] + k(vi, vj)
previous[vj] := vi
Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem). Di bawah ini merupakan penerapan algoritma dijkstra pada graf yang mempunyai 11 vertices dengan bobot masing-masing yang mewakili jarak antar verteks. Vertices pada graf dapat mewakili suatu tempat atau ring road pada suatu wilayah geografis.
Dalam penentuan jalur terpendek pada graf di atas di butuhkan titik awal dan titik tujuan. Misalkan titik awal D dengan titik tujuan F dengan diagram pohon kita dapat mengetahui jalur mana yang dapat dilalui, dengan ketentuan jalur jalan yang telah dilalui dengan rute yang sama tidak boleh dilalui lagi dan jika telah sampai pada titik tujuan maka pencarian pada rute tersebut berhenti dan melanjutkan dengan rute lain, jika semua rute telah dilalui kita dapat mengambil kesimpulan rute mana yang akan dilalui dengan jarak yang optimum atau terpendek.
Dari diagram pohon tersebut dapat ditentukan rute yang berhasil mencapai tujuan dari vertices D ke vertices F yaitu :
D ⇨A ⇨ B ⇨F dengan total jarak = 10
D ⇨A ⇨ G ⇨ B⇨ F dengan total jarak = 18
D ⇨C ⇨ B ⇨F dengan total jarak = 13
D ⇨E ⇨F dengan total jarak = 9
Dari hasil tersebut jarak terpendek adalah D ⇨E ⇨F dengan total jarak 9. Dalam penerapan algoritma dijkstra pada graf di atas merupakan graf tidak berarah, tetapi algoritma Dijkstra dapat juga diterapkan pada graf berarah
