Set Instruksi
Set Instruksi(bahasa Inggris: Instruction Set, atau Instruction Set Architecture (ISA)) didefinisikan sebagai :
Suatu aspek dalam arsitektur komputer yang dapat dilihat oleh para pemrogram. Secara umum, ISA ini mencakup jenis data yang didukung, jenis instruksi yang dipakai, jenis register, mode pengalamatan, arsitektur memori, penanganan interupsi, eksepsi, dan operasi I/O eksternalnya (jika ada).
ISA merupakan sebuah spesifikasi dari kumpulan semua kode-kode biner (opcode)yang diimplementasikan dalam bentuk aslinya (native form) dalam sebuah desain prosesor tertentu. Kumpulan opcode tersebut, umumnya disebut sebagai bahasa mesin (machine
language) untuk ISA yang bersangkutan. ISA yang populer digunakan adalah set instruksi untuk chip Intel x86, IA-64, IBM PowerPC, Motorola 68000, Sun SPARC, DEC Alpha, dan lain-lain. ISA kadang-kadang digunakan untuk membedakan kumpulan karakteristik yang disebut di atas dengan mikroarsitektur prosesor, yang merupakan kumpulan teknik desain prosesor untuk mengimplementasikan set instruksi (mencakup microcode, pipeline, sistem cache, manajemen daya, dan lainnya). Komputer-komputer dengan mikroarsitektur berbeda dapat saling berbagi set instruksi yang sama. Sebagai contoh, prosesor Intel Pentium dan prosesor AMD Athlon mengimplementasikan versi yang hampir identik dari set instruksi Intel x86, tetapi jika ditinjau dari desain internalnya, perbedaannya sangat radikal.
Konsep ini dapat diperluas untuk ISA-ISA yang unik seperti TIMI yang terdapat dalam IBM System/38 dan IBM IAS/400. TIMI merupakan sebuah ISA yang diimplementasikan sebagai perangkat lunak level rendah yang berfungsi sebagai mesin virtual. TIMI didesain untuk meningkatkan masa hidup sebuah platform dan aplikasi yang ditulis untuknya, sehingga mengizinkan platform tersebut agar dapat dipindahkan ke perangkat keras yang sama sekali berbeda tanpa harus memodifikasi perangkat lunak (kecuali yang berkaitan dengan TIMI). Hal ini membuat IBM dapat memindahkan platform AS/400 dari arsitektur mikroprosesor CISC ke arsitektur mikroprosesor POWER tanpa harus menulis ulang bagian-bagian dari dalam sistem operasi atau perangkat lunak yang diasosiasikan dengannya. Ketika mendesain mikroarsitektur, para desainer menggunakan Register Transfer Language (RTL) untuk mendefinisikan operasi dari setiap instruksi yang terdapat dalam ISA. Sebuah ISA juga dapat diemulasikan dalam bentuk perangkat
lunak oleh sebuah interpreter. Karena terjadi translasi tambahan yang dibutuhkan untuk melakukan emulasi, hal ini memang menjadikannya lebih lambat jika dibandingkan dengan menjalankan program secara langsung di atas perangkat keras yang mengimplementasikan ISA tersebut. Akhir-akhir ini, banyak vendor ISA atau mikroarsitektur yang baru membuat perangkat lunak emulator yang dapat digunakan oleh para pengembang perangkat lunak sebelum implementasi dalam bentuk perangkat keras dirilis oleh vendor.
Daftar ISA di bawah ini tidak dapat dikatakan komprehensif, mengingat banyaknya arsitektur lama yang tidak digunakan lagi saat ini atau adanya ISA yang baru dibuat oleh para desainer.
ISA
yang diimplementasikan dalam bentuk perangkat keras :
* Alpha AXP (DEC Alpha)
* ARM (Acorn RISC Machine) (Advanced RISC Machine now ARM Ltd)
* IA-64 (Itanium/Itanium 2)
* MIPS
* Motorola 68k
* PA-RISC (HP Precision Architecture)
* IBM POWER
* IBM PowerPC
* SPARC
* SuperH (Hitachi)
* System/360
* Tricore (Infineon)
* Transputer (STMicroelectronics)
* VAX (Digital Equipment Corporation)
* x86 (IA-32, Pentium, Athlon) (AMD64, EM64T)
ISA
yang diimplementasikan dalam bentuk perangkat lunak lalu dibuat perangkat
kerasnya
* p-Code (UCSD p-System Version III on Western Digital Pascal Micro-Engine)
* Java virtual machine (ARM Jazelle, PicoJava)
* FORTH
ISA
yang tidak pernah diimplementasikan dalam bentuk perangkat keras
* SECD machine
* ALGOL Object Code
Teknik Pengalamatan
Untuk menyimpan data ke dalam memori komputer, tentu memori tersebut diberi identitas (yang disebut dengan alamat/address) agar ketika data tersebut diperlukan kembali, komputer bisa mendapatkannya sesuai dengan data yang pernah diletakkan di sana.
Untuk media penyimpanan yang bersifat sequential access storage device (SASD) seperti kaset (magnetic tape),alamat tersebut tidak terlalu dipusingkan karena pasti data disimpan secara berurutan (sequential/ consecutive) mulai dari depan hingga ke akhir bagian dari pita kaset. Begitu juga dengan data yang diorganisasi secara sequential, di alamat manapun data disimpan, data akan tetap diakses secara berurutan pula, mulai dari record pertama hingga ke record terakhir.
Lain halnya dengan data yang diorganisasi secara relative yang disimpan di media penyimpanan yang bersifat direct access storage device (DASD), karena data yang akan diraih kembali, dituju langsung ke alamatnya tanpa melalui records lainnya (belum tentu dimulai dari data yang paling awal disimpan), maka alamat memori memegang peranan penting. Untuk itu, di catatan ini akan diterangkan beberapa cara melakukan
penempatan data di memori agar kelak dapat diraih kembali dengan tepat, yang diberi
judul “Teknik Pengalamatan.”
Teknik pengalamatan ini hampir sudah tidak diperlukan lagi oleh pemakai komputer saat ini karena hampir seluruh software yang beredar di pasaran tidak mengharuskan si pemakai menentukan di alamat mana datanya akan disimpan (semua sudah otomatis dilakukan oleh si software). Jadi, yang kita pelajari adalah bagaimana kira-kira si software tersebut melakukan teknik pengalamatannya, sehingga data yang sudah kita berikan dapat disimpan di alamat memori tertentu dan dapat diambil kembali dengan tepat.
Ada 3 teknik dasar untuk
pengalamatan, yakni 1. Pemetaan langsung (direct mapping) yang terdiri dari dua
cara yakni Pengalamatan Mutlak (absolute addressing) dan Pengalamatan relatif
(relative addressing), 2. Pencarian Tabel (directory look-up), dan 3. Kalkulasi
(calculating).
A. TEKNIK PEMETAAN LANGSUNG
1. PENGALAMATAN MUTLAK
Pandang, kita memiliki data teman-teman sekelas kita yang akan kita masukkan ke dalam memori (misal hard disk), data tersebut berjumlah 50 orang yang masing-masing terdiri atas atribut-atribut : NIM, NAMA, dan ALAMAT_RUMAH. Jika data tersebut kita masukkan dengan organisasi file sequential, maka jika kita mencari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat di ‘Jl. Margonda No. 100, Depok’, maka pencarian akan dilakukan mulai dari record pertama (data pertama yang dimasukkan), dan seterusnya menuju ke record terakhir sampai ketemu data yang dicari tersebut.
Lain halnya jika data tersebut dimasukkan dengan organisasi file relative, maka data tersebut akan didapat secara langsung dari record yang dituju. Tentu, untuk langsung mendapatkan record yang dituju ada ‘sesuatu’ yang disebut dengan kunci atribut (key field). Kunci atribut itulah yang dikelola sedemikian rupa sehingga ‘kita’ bisa tahu
dimana record tersebut disimpan. Untuk teknik pengalamatan ‘alamat mutlak’ ini, kita tidak terlalu mempermasalahkan kunci atribut karena kita diminta langsung menuliskan di mana alamat record yang akan kita masukkan. Jika kita menggunakan hard disk atau magnetic drum, ada dua cara dalam menentukan alamat memorinya, yaitu (1) cylinder addressing dan (2) sector addressing. Jika kita menggunakan cylinder addressing, maka kita harus menetapkan nomor-nomor dari silinder (cylinder), permukaan (surface), dan record, sedangkan bila kita menggunakan sector addressing, maka kita harus menetapkan nomor-nomor dari sektor (sector), lintasan (track), dan permukaan (surface). Teknik ini mudah dalam pemetaan (pemberian) alamat memorinya. Sulitnya pada pengambilan (retrieve) data kembali, jika data yang kita masukkan banyak, kita bisa lupa di mana alamat record tertentu, misalkan apakah kita ingat nomor record dari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat di ‘Jl. Margonda No. 100,
Depok’ ?, apakah kita harus menghafal selamanya alamat-alamat tersebut ?.
Pelajari keuntungan dan kerugian lainnya.
Teknik ini dapat dijuluki dengan device dependent (tergantung pada peralatan rekamnya), artinya, kita tidak dapat begitu saja meng-copy data berkas ini ke komputer lainnya, karena mungkin saja di komputer lainnya itu menggunakan alat rekam yang berbeda spesifikasinya.
Teknik ini juga dapat dijuluki dengan address space dependent (tergantung pada alamat-alamat yang masih kosong), artinya, kita tidak dapat begitu saja meng-copy data berkas ini ke komputer lainnya, karena mungkin saja di komputer lainnya itu alamat-alamat yang dibutuhkan sudah tidak tersedia lagi.
2. PENGALAMATAN RELATIF
Teknik ini menjadikan atribut kunci sebagai alamat memorinya, jadi, data dari NIM dijadikan bertipe numeric(integer) dan dijadikan alamat dari record yang bersangkutan. Cara ini memang sangat efektif untuk menemukan kembali record yang sudah disimpan, tetapi sangat boros penggunaan memorinya. Tentu alamat memori mulai dari 1 hingga alamat ke sekian juta tidak digunakan karena nilai dari NIM tidak ada
yang kecil. Pelajari keuntungan dan kerugian lainnya.Teknik ini termasuk dalam katagori address space dependent.
3. TEKNIK PENCARIAN TABEL
Teknik ini dilakukan dengan cara, mengambil seluruh kunci atribut dan alamat memori yang ada dan dimasukkan ke dalam tabel tersendiri. Jadi tabel itu (misal disebut dengan tabel INDEX) hanya berisi kunci atribut (misalkan NIM) yang telah disorting (diurut) dan alamat memorinya. Jadi, sewaktu dilakukan pencarian data, tabel yang pertama dibaca adalah tabel INDEX itu, setelah ditemukan atribut kuncinya, maka data alamat yang ada di sana digunakan untuk meraih alamat record dari data (berkas/ file/ tabel) yang sebenarnya. Pencarian yang dilakukan di tabel INDEX akan lebih cepat dilakukan dengan teknik pencarian melalui binary search (dibagi dua-dua, ada di mata kuliah Struktur dan Organisasi Data 2 kelak) ketimbang dilakukan secara sequential. Nilai key field (kunci atribut) bersifat address space independent (tidak terpengaruh terhadap perubahan organisasi file-nya), yang berubah hanyalah alamat yang ada di INDEX-nya.
4. TEKNIK KALKULASI ALAMAT
Kalau pada teknik pencarian tabel kita harus menyediakan ruang memori untuk menyimpan tabel INDEX-nya, maka pada teknik ini tidak diperlukan hal itu. Yang dilakukan di sini adalah membuat hitungan sedemikian rupa sehingga dengan memasukkan kunci atribut record-nya, alamatnya sudah dapat diketahui. Tinggal masalahnya, bagaimana membuat hitungan dari kunci atribut itu sehingga hasilnya bisa efisien (dalam penggunaan memori) dan tidak berbenturan nilainya (menggunakan alamat yang sama). Misal, untuk data si ALI di atas yang memiliki NIM = ‘10105787’, di mana akan kita letakkan ?. Bila yang kita lakukan adalah perhitungan : INT(VAL(NIM)/1000000) maka haslinya adalah 10, dengan demikian data si ALI akan disimpan di alamat 10. Tapi, apakah alamat 10 itu tidak akan digunakan oleh data lain dengan perhitungan yang sama ?, ternyata tidak. Untuk data si BADU yang NPMnya ’10105656’ juga di alamat
tersebut, dan ternyata masih banyak juga yang ’rebutan’ untuk menempati alamat tersebut jika dilakukan dengan perhitungan seperti di atas. Perhitungan (kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu alamat disebut dengan fungsi hash. Bisa juga fungsi hash digabungkan dengan teknik pencarian seperti tabel
di atas, tetapi akan menjadi lebih lama pengerjaannya dibanding hanya dengan satu jenis saja (fungsi hash saja atau pencarian tabel saja). Fungsi hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki kelas ekivalen (synonim) yang
kecil, atau sederhananya, memiliki kalkulasi yang mudah tetapi memiliki benturan alamat yang sedikit. Ada beberapa cara untuk mengatasi benturan (collision) penggunaan alamat seperti di atas, antara lain : scatter diagram techniques, randomizing techniques, key to address transformation methods, direct addressing techniques, hash tables methods, dan hashing. Di sini, kita hanya membahas mengenai hashing. Beberapa fungsi hash yang umum digunakan adalah : division remainder, mid square, dan folding.
5. DIVISION REMAINDER
Idenya adalah, membagi nilai key field dengan nilai tertentu, dan sisa pembagian tersebut dijadikan alamat relatifnya. Nilai tertentu itu terserah kita, ada yang membagi dengan bilangan prima, namun ada juga yang tidak.Yang jelas, tujuannya adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan yang bakal terjadi. Ada perhitungan faktor muat (load factor) yaitu, jika kita memiliki sejumlah record yang akan ditempatkan ke dalam memori, maka setidaknya kita harus menyediakan memori yang kapasitasnya melebihi dari jumlah record tersebut. Misalkan, kita memiliki 4000 record, maka sebaiknya kita memiliki memory space sebanyak 5000 alamat. Faktor muat dihitung dengan cara membagi jumlah record dalam file dengan jumlah maksimum record dalam file (alamat yang tersedia). Semakin besar nilai faktor muat maka semakin baik teknik ini digunakan. Faktor muat untuk contoh di atas adalah 4000/5000 = 0,8.
6. MIDSQUARE
Teknik ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. Misalkan, nilai key-nya = 123456790, setelah dikuadratkan hasilnya = 15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi, alamat memori untuk data tersebut di 8997.
7. HASING BY FOLDING
Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan). Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :
0976
2345
1
——–+
4321
Maka, alamat dari data tersebut adalah di 4321.Berbagai teknik dalam penentuan penempatan data di memori (sekunder) komputer terus berkembang. Tentu saja karena data yang direkam biasanya selalu bersifat dinamis (bisa bertambah, berkurang, di-copy, di-sorting) dan sebagainya. Kedinamisan tersebut tentu saja bisa berpengaruh terhadap alamat-alamat yang sudah ditetapkan sebelumnya yang bersifat fixed size space atau memiliki ukuran alamat yang tetap (satu misalnya, jika kita meng-copy data tersebut yang semula di hard disk ke dalam disket, apakah alamat-alamat yang tersedia di disket sama dengan di hard disk ?, tentu tidak). Teknik hash baru yang dikembangkan antara lain dynamic hashing, extendible hashing, dan virtual hashing. Tujuannya adalah agar alamat-alamat yang sudah ada tidak berubah meskipun data baru ditambahkan dengan cara membagi-bagi memori menjadi bagian-bagian tertentu yang disebut dengan blok atau bucket, bila sebuah record akan dimasukkan ke dalam
bucket yang sudah penuh, maka bucket baru disediakan kembali. Dynamic hashing memakai struktur indeks binary tree untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Extendible hashing menggunakan direction untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan.
Sedangkan virtual hashing lebih luas lagi, termasuk di dalamnya dynamic hashing dan extendible hashing dan berbagai teknik indeks lainnya (yang tidak dibahas di sini).
8. PENDEKATAN MASALAH BENTURAN (COLLISION)
Hampir semua teknik akan mengalami benturan dalam penggunaan alamat memorinya. Ada beberapa teknik untuk menyelesaikannya, yaitu linear probing dan separate overflow.
9. LINEAR PROBING
Metode ini dilakukan dengan cara :
apabila hasil perhitungan key baru ternyata sama dengan hasil perhitungan key sebelumnya, maka dengan menambahkan hasil perhitungan tersebut dengan satu (per satu) (secara linear) sampai ke alamat memori yang masih kosong, ia akan menempati alamat tersebut.
Misal, hasil perhitungan adalah 300 sedangkan di alamat 300 sudah ada yang menempati, maka data baru akan menempati alamat 301, bila alamat tersebut juga sudah ada yang menempati, maka ia akan menempati alamat 302, dan seterusnya bertambah satu-satu hingga ke alamat yang masih kosong (belum ditempati). Hal semacam ini disebut dengan open addressing. Begitu juga ketika data tersebut dipanggil kembali, maka jika tidak ketemu di home address-nya (hasil perhitungan awalnya), maka akan ditambahkan dengan satu per satu hingga di alamat tertentu yang recordnya memiliki nilai key sama dengan nilai key yang dicari.
10. DOUBLE HASHING
Dari namanya dapat diketahui bahwa double hashing adalah menjalankan fungsi hash yang kedua terhadap hasil fungsi hash yang pertama jika masih terjadi collision. Penempatan data dapat dilakukan di primary area atau home address-nya (hasil perhitungan sebenarnya, nilai interval yang mungkin dapat dijangkau dengan perhitungannya), atau di separate overflow area (area yang disediakan untuk menampung data yang berbenturan/di luar area yang masuk dalam interval nilai perhitungannya). Double hashing lebih baik dari linear probing pada faktor muat tinggi (lebih dari 0,8), dan sama baik pada faktor muat 0,5. Double hashing memiliki synonim (hasil perhitungan yang sama/terjadi collision) berpencar sedangkan linear probing mengelompok pada faktor muat kurang dari 0,5.
11. SYNONIM CHAINING
Synonim chaining adalah suatu rangkaian pointer yang menghubungkan (link) antara satu alamat dengan alamat lain yang berada di separate overflow area. Hal ini dilakukan untuk mempercepat akses di area tersebut. Jadi, jika hasil perhitungan ternyata datanya bukan yang data dicari, maka akan di-link data yang berada di separate overflow area mulai dari awal alamatnya hingga ketemu data yang dicarinya.
12. BUCKET ADDRESSING
Cara lain untuk menghindari benturan adalah pembuatan blok-blok memori. Misalkan, setiap 10 record akan kita tempatkan di dalam satu blok (bucket). Jika blok tersebut sudah penuh, maka dibuka kembali blok-blok lain. Perhitungan penempatan record ke dalam blok dapat dilakukan dengan teknik yang mirip dengan teknik-teknik sebelumnya.
Begitu juga dengan pengambilan data kembali (retrieve) dilakukan dengan teknik-teknik yang sama dengan sebelumnya. Istilah prime memory (memori yang ditempati oleh record yang sesuai dengan hasil perhitungannya) dan separate overflow (memori yang menampung record yang hasil perhitungannya berbenturan sehingga tidak bisa ditempatkan di memori sebenarnya) dipakai juga di sini. Istilahnya menjadi : primary bucket dan overflow bucket.
13. FILE ORGANIZATION : INDEX SEQUENTIAL
Selain organisasi berkas sequential dan relative yang telah dibahas sebelumnya, berikut akan dibahas mengenai organisasi berkas index sequential. Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi)nya. Jadi, file organization index sequential adalah file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan sequential. Ada dua pendekatan dasar dalam menyusun organisasi berkas semacam ini, yaitu (1) blok index dan data, dan (2)
prime dan overflow data area. Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index (daftar isi dalam buku kamus) diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer). Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 5 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yang akan mendapatkan record yang dicari secara direct (lihat skema di buku referensi hal. 60). Bila dilakukan penyisipan data dan blok tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/padding lagi), maka akan dilakukan reorganisasi blok dengan membentuk blok baru.Tentu, mungkin saja perubahan ini akan berdampak pada isi blok index-nya.
Pendekatan kedua adalah dengan lebih memperhatikan aspek karakteristik dari hardware (fisik) alat penyimpanan datanya. Biasanya disimpan di hard disk yang memiliki cylinder dan track. Caranya hampir sama dengan cara di pendekatan pertama, hanya di sini lebih ditekankan pada aspek fisik. Jadi, yang bertingkat-tingkat adalah cylender-nya dan blok datanya ditulis secara consecutive di setiap track (misalkan 1
cylinder berisi 4 track, nomor 0 sampai 3). Index (pencarian data) tertinggi disebut dengan master index, dari master index berturut-turut menuju ke blok-blok index tingkat berikutnya hingga meraih record data yang berada di track-nya. Bila dilakukan penyisipan data dan track tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/padding lagi), maka akan dilakukan reorganisasi track dengan membentuk track baru. Tentu, track baru itu di luar prime data file-nya, yaitu di overflow data area-nya.
14. FILE ORGANIZATION : MULTI KEY
Selain organisasi berkas sequential, relative, dan index sequential yang telah dibahas sebelumnya, berikut akan dibahas mengenai organisasi berkas multi key. Inti dari organisasi berkas ini adalah, sebuah berkas (file) harus dapat diakses secara langsung (direct) dari berbagai kunci atribut (key field) yang ditentukan. Misalkan file MAHASISWA yang berisi biodata mahasiswa, harus bisa dicari record data seorang mahasiswa berdasarkan NPMnya, atau NAMAnya atau mungkin ALAMATnya. Organisasi berkas seperti ini sangat diperlukan karena berbagai user akan membutuhkan data yang sama dengan cara pandang yang berbeda. Sayangnya, jarang software database yang bisa
melakukan hal ini (menyediakan fasilitas pengorganisasian berkasnya secara multi key).
Ada banyak cara untuk mengorganisasi berkas semacam ini, misalkan dengan cara
(1) inversion, dan (2) multi-list. Cara inversion mirip dengan organisasi relative yang satu tabel index-nya berisi key field yang terurut dan sebuah pointer yang menunjuk ke alamat di mana data disimpan. Bedanya, karena di sini dibutuhkan banyak kunci, maka di tabel tersebut disimpan pula kunci-kunci atribut lainnya yang dibutuhkan. Cara kedua (multi-list) hampir sama dengan cara pertama, yaitu dibuat tabel index yang terurut key field-nya dan penunjuk ke nomor record (pertama) datanya, hanya di setiap record ditambahkan pointer (penunjuk) ke record-record berikutnya sesuai urutan key field yang ditentukannya. Tentu penunjuk itu akan berubah datanya bila akses dilakukan dengan key field lainnya.
15. SORT dan MERGE FILE
Banyak kebutuhan agar data harus diurut (sort), yang paling sederhana adalah ketika kita akan mencetak absensi mahasiswa. Jika data dicetak tanpa diurut, maka akan dibutuhkan waktu yang lebih lama bagi mahasiswa untuk mencari datanya di lembar absensinya. Padahal, sewaktu memasukkan data ke komputer dulu, kecil kemungkinan data diurut terlebih dulu secara manual karena data calon mahasiswa yang membayar uang kuliah dan menjadi mahasiswa juga tidak urut abjad. Sortir yang dilakukan di komputer jaman sekarang umumnya cukup dilakukan di dalam memori utama komputer (internal sort), sedangkan pada masa lalu, sortir dilakukan sebagian-sebagian dengan
bantuan memori sekunder (sebagai penampung sementara) sebelum akhirnya semua akan (di-merge) dan direkam ke memori sekunder itu.
Faktor-faktor yang mempengaruhi metode eksternal sort adalah : (1) jumlah record yang akan akan disortir, (2)ukuran (panjang) record, (3) jumlah storage yang digunakan, (4) kapasitas memori internal, dan (5) distribusi nilai key dalam input file.
Berbagai macam teknik sort/merge file adalah (1) natural merge, (2) balanced merge, (3) polyphase merge, dan (4) cascade merge.
16. NATURAL MERGE
M-natural merge adalah sebanyak m-input file yang akan disortir/ merge untuk menghasilkan 1 buah output file yang sudah terurut. Contoh, untuk mengurut 6000 record data tetapi memori utama komputernya hanya dapat menampung 2000 record, maka file tersebut akan dijadikan 3 input file (3-way natural merge) yang akhirnya kembali disimpan menjadi sebuah output file yang sudah terurut.
17. BALANCE MERGE
Balance merge hampir sama dengan natural merge, namun kondisi awalnya adalah banyaknya input file seimbang dengan banyaknya output file (m-way balance merge berarti m-input file dan m-output file), meskipun pada akhirnya tidak demikian.
18. POLYPHASE MERGE
Polyphase merge merupakan teknik perbaikan dari balance merge dengan cara memanfaatkan file yang nganggur (idle) ketika dilakukan merge. Pada m-polyphase merge digunakan 2m-1 input file dan 1 output file.
19. CASCADE MERGE
Cascade merge merupakan teknik merge yang selalu mengurangi 1 file input pada setiap tahapnya. Jadi, jika digunakan m-way cascade merge, maka file input yang digunakan adalah 2m-1,kemudian 2m-2,2m-3, dan seterusnya hingga bernilai 2 input file.
BEBERAPA ISTILAH DALAM SISTEM
OPERASI YANG TERKAIT DENGAN SISTEM BERKAS
Kita (programmer) tidak dapat berbuat apa-apa tanpa adanya sistem operasi di komputer. Sistem operasi membantu kita untuk mengontrol alat-alat (devices) komputer agar bekerja dengan baik. Misalkan, kita minta ”SAVE” data atau ”WRITE” data kita ke disket, maka sistem operasi akan membuka jalur transportasi (pathway) data dari hard disk ke memori utama dan dilanjutkan ke disket. Bukan itu saja, jika kita minta ”PRINT” maka sistem operasi mengaktifkan printer dan melakukan ”READ” data yang akan
dicetak dari alat penyimpanannya dan kembali ”mengangkut” data tersebut hingga akhirnya ke printer, dan sebagainya.
Beberapa istilah dalam sistem operasi antara lain :
(1) Supervisor I/O : adalah bagian dari sistem operasi yang mengontrol peralatan input/ output (I/O) computer.
(2) File manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur pemberkasan di dalam alat-alat penyimpanan data di komputer.
(3) Device manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur alat-alat (piranti-piranti) yang ada di dalam konfigurasi komputernya.
(4) I/O channel : adalah prosesor yang telah diprogram untuk mengakses peralatan yang dibutuhkan dan mengontrol jalur data.
(5) Selector channel : mengatur aliran data antara memori utama dengan peralatan lain seperti disk (peralatan dengan kecepatan tinggi).
(6) Multiplexer channel : mengatur aliran data antara memori utama dengan peralatan-peralatan lain seperti printer, magnetic tape, dsb. (peralatan dengan kecepatan rendah).
(7) Block multiplexer channel : mengatur aliran data ke berbagai peralatan.
(8) Dedicated device : peralatan yang hanya dapat digunakan oleh seorang pemakai dalam satu saat.
(9) Shared device : peralatan yang bisa digunakan oleh satu atau lebih pemakai dalam satu saat (waktu yang bersamaan).
(10) Spooling : dukungan peralatan virtual I/O yang biasanya digunakan di komputer multiuser. Misalkan 10 orang user akan mencetak ke sebuah printer dalam waktu bersamaan, maka spooling dapat menampung antrean mana urutan yang akan dicetak terlebih dulu dan mana yang kemudian.
(11) Buffer : adalah bagian dari CPU yang bertugas untuk menampung data sementara dari dan/ atau ke main memory.
Contoh, ketika kita ’membakar (burn)’ CD data, maka data yang ada di disk akan ditampung ke buffer terlebih dulu sebelum ditulis ke CD.
(12) Single buffering : (buffer tunggal), jika kita memiliki data sebesar 1MB yang akan dicetak dan buffer hanya dapat menampung 256KB, maka data 1MB tersebut diletakkan ke buffer sebesar 256KB dulu, baru dicetak hingga selesai 256KB itu, kemudian data diambil kembali untuk mengisi buffer itu, dan seterusnya.
(13). Anticipatory buffering : pada (12) ada waktu tunggu antara pencetakan isi buffer hingga buffer kosong dengan pengisian kembali buffer itu. Karenanya, sistem kontrol I/O dibuat sedemikian rupa sehingga sebelum buffer sampai benar-benar kosong sudah dimuat lagi dengan data yang baru.
(14) Double buffering : (buffer ganda), digunakan untuk meniadakan waktu tunggu seperti di single buffer, karena, ketika isi dari buffer 1 dicetak, buffer 2 diisi data. Ketika buffer 1 selesai dicetak, maka ia akan diisi data, sementara isi buffer 2 mulai dicetak. Demikian seterusnya.
(15) Multiple buffering : untuk mengantisipasi kemungkinan pengisian buffer kalah cepat dengan pengosongan buffer sehingga diharapkan tidak ada waktu tunggu yang kemungkinan masih ada di (14).
Tambahan istilah :
(1) completely inverted file adalah file yang memiliki index inversi untuk setiap fieldnya.
(2) partialy inverted file adalah file yang minimal satu fieldnya memiliki index inverse.
(3) primary key adalah atribut (field) yang dipilih untuk menentukan struktur storage pada organisasi file multi key, adapun key lainnya disebut dengan secondary key.
(4) head switching adalah waktu yang dibutuhkan untuk head dari hard disk ke track dan permukaan yang tepat.
(5) seek time adalah waktu yang digunakan untuk menggerakkan tangkai penghubung head dari hard disk ke posisi silinder yang tepat.
(6) parity check adalah sebuah track dalam tape yang digunakan untuk menyimpan kesalahan data.
(7) hit ratio adalah perbandingan antara banyaknya record yang akan diakses dengan banyaknya record dalam sebuah file. Semakin tinggi nilainya, semakin baik sequential digunakan.
Desain Set Komputer
Mesin Von Neumann
Sebagian besar, atau mungkin semua, komputer yang anda kenal adalah Von Neumann machines (mesin von Neumann), Dalam sebagian besar konteks, istilah computer dan Von Neumann machine adalah sinonil. (mesin von Neumann) jika komputer tersebut memenuhi kriteria berikut:
a) Ia mempunyai tiga subsistem hardware dasar:
1) sebuah CPU
2) sebuah sistem memori utama
3) sebuah sistem I/O
b) Ia merupakan komputer stored-program (program tersimpan).
Sistem memori utama menyimpan program yang mengontrol operasinya, dan komputer dapat
mengubah programnya sendiri untuk menambah atau mengurangi data lain yang ada di dalam memori.
c) Ia menjalankan instruksi secara berurutan.
CPU menjalankan,atau setidaknya akan menjalankan, satu operasi dalam sekali waktu.
d) Ia mempunyai, atau paling tidak akan mempunyai, satu path antara sistem memoriutamadan unit kontrolCPU ; hal ini biasanya dinamakan "Von Neumann Bottleneck."
Harvard architecture termasuk dalam kelompok mesin yon Neumann Harvard architecture (arsitektur Harvard) memungkinkan CPU untuk mengakses instruksi dan data secara serentak.
Komponen utama CPU adalah:
a) Control unit (CU), yang mengontrol operasi komputer.
b) Arithmetic dan logic unit (ALU), yang menjalankan operasi aritmetik, logika,
dan shift untuk menghasilkan sesuatu.
c) Register set, yang menyimpan berbagai macam nilai selama operasi komputer.
Program counter (PC) (kadang-kadang disebut sebagai instruction counter),
yang menyimpan alamat memori utarna dari suatu instruksi. PC adalah bagian
dari register set (set register).
Arsitektur Harvard
Setiap instruksi mempunyai operation code (op code), yaitu kode angka yang biasanya bisa dijumpai pada field pertama dari instruksi, yang memberitahu komputer
mengenai operasi yang akan dijalankannya. Program adalah urutan instruksi yang akan dijalankan komputer.
Urutan instruksi yang dijalankan komputer adalah instruction stream. Untuk menjaga track instruksi dalam memori, mesin von Neumann menggunakanPC. PC ini "points to" (menyimpanalamat dari) instruksiberikutnyayang akan dijalankan. terus menerus: instruction fetch dan instruction execution. Urutan ini dinamakan Untuk meningkatkan kecepatan eksekusi, arsitek biasanya menerapkan arsitektur Von Neumann dengan prosesor pipelined. Arsitek juga menggunakan beberapa unit aritmetik untuk meningkatkan kecepatan CPU, dan ia menyertakan buffer (memori berkecepatan tinggi tingkat menengah), agar kecepatan prosesor sesuai dengan kecepatan memori.
Mesin non-van Neumann
Tidak semua komputer merupakan mesin von Neumann. Flynn, pada tahun 1966, mengklasifIkasikan arsitektur komputer menurut berbagai sifatnya, yang meliputi jumlah prosesor, jumlah program yang dapat dijalankan, dan struktur memori.
KlasifIkasinyaitu mencakup kategori berikut :
a) Single instructionstream, single data stream (SISD) satu aliran instruksi, satu
aliran data. Arsitektur von Neumann termasuk dalam klasifIkasi ini. Komputer SISD mempunyai satu CPU yang menjalankan satu instruksi pada sekali waktu (oleh karenanya disebut aliran instruksi tunggal) dan menjemput atau menyimpan satu item data pada sekali waktu (oleh karenanya disebut aliran data tunggal).
b) Single instruction stream, multiple data stream (SIMD satu aliran instruksi, beberapa aliran data. Array prosesor termasuk dalam kategori ini. Mesin SIMD mempunyai sebuah CU yang beroperasi seperti mesin von Neumann (yaitu, ia menjalankan satu aliran instruksi), CU menghasilkan signal kontrol untuk semua PE, yang menjalankan operasi yang sama, biasanya pada lockstep, pada item data yang berbeda (oleh karenanya disebut aliran data banyak).
c) Multiple instruction stream, single data stream (MISD) beberapa a1iran instruksi,
satu aliran data. Secara logis, mesin dalam kelompok ini akan menjalankan berbagai program pada item data yang sama. walaupun beberapa sistem MIMD bisa digunakan dengan cara ini.
d) Multiple instruction stream, multiple data stream (MIMD) beberapa aliran instruksi, beberapa aliran data. Mesin MIMD juga disebut multiprosesor. Ia mempunyai lebih dari satu prosesor independen, dan setiap prosesor dapat menjalankan program yang berbeda (oleh karenanya disebut aliran data banyak) pada datanya sendiri (oleh karenanya disebut aliran data banyak).
Mesin SIMD dan MIMD adalah parallel processor (prosesor paralel), karena mereka beroperasi secara paralel pada lebih dari satu data sekali waktu. Arsitektur
multiprosesor dapat dibagi menjadi dua kategori, didasarkan pada susunan sistem
memorinya:
a) Global memory (GM) system architecture! arsitektur sistem memori global. Satu sistem memoriglobal digunakanbersamaoleh semua prosesor. Arsitektur komputer berunjuk kerja tinggi pada saat ini adalah dari jenis ini, dan ketiga arsitektur yang ada pada Gb. 13 ditunjukkan dengan memori global.
b) Local-memory(LM) systemarchitecture! Arsitektur sistem memori lokal. Disini, satu sistem penyimpanan digunakan untuk setiap prosesor. Multiprosesor dengan LM mungkin juga mempunyai GM dan juga disebut multiple processor.
2 ( dua ) jenis prosesor paralel (SIMD dan MIMD)
Mesin SIMD
Komputer SIMD mempunyai sifat berikut ini:
a) Mereka mendistribusikanpemrosesan ke sejumlah hardware.
b) Mereka beroperasi secara.bersama-sama pada beberapa elemen data yang berbeda.
c) Mereka menjalankan komputasi yang sarna pada semua e1emen data.
Oalammesin SIMO,PE mereka mengakses memori dengan cara yang berbeda. PE-PE dari komputer GM-SIMD secara bersama menggunakan sistem penyimpanan yang sarna, sedangkan PE-PE dari komputer LM-SIMO mempunyai sistem penyimpanan independen.
Array prosesor adalah arsitektur SIMO. Ia mempunyai satu CD dan beberapa PE. CD tersebut menghasilkan signal kontrol untuk semua PE, yang menjalankan komputasi yang tepat sarna secara serentak, namun dengan data yang berbeda. Biasanya, CD itu sendirilah yang mempakan komputer yon Neumann, yaitu merupakan komputer khusus yang lengkap yang mempunyai set register, ALD, dan unit kontrol. Komputer inf dinamakan sebagai unit kontrol (control unit), karena ia semata-mata dirancang untuk mengontrol PE dalam array prosesor, dan bukan untuk beroperasi sebagai komputer yang berdiri sendiri.
Mesin MIMD
Komputer MIMD mempunyai sifat berikut ini:
a) Mereka mendistribusikanpemrosesan ke sejumlah prosesor independen.
b) Mereka membagikansumber,termasukmemoriutama, ke prosesorkomponen.
c) Setiap prosesor beroperasi secara independen dan bersarna-sarna.
Setiap prosesor menjalankan programnya sendiri. Arsitektur MIMD yang berbeda mempunyai interconnection network yang berlainan, prosesor yang berbeda, struktur pengalamatan memori yan'g berbeda, dan struktur sinkronisasi dan kontrol yang berbeda
Kita dapat mengkategorikan komputer multiple-prosesor sebagai tightly coupled atau loosely coupled, Prosesor dalam multiprosesor yang terangkai dengan ketat (tightly coupled) biasanya menggunakan secara bersama satu sistem memori. Prosesor yang ada dalam multiprosesor yang terangkai dengan longgar (loosely coupled) mungkin juga menggunakan satu sistem memori, Jadi, komputer yang terangkai dengan ketat dan YaIJ.gterangkai dengan longgar secara berturut-turut sesuai dengan klasifIkasi GM-MIMD dan LM-MIMD.
Karena sebagian besar komputer tujuan khusus mencakupprosesor I/O tujuan khusus independen,maka secara logis kita dapat menganggapnya sebagai arsitektur GM-MIMD.
Processors with local memory Category Common Name Examples SISD (CISC) Uniprocessor ffiM PC, DEC PDP-ll, DEC VAX-II SISD (RISC) Uniprocessor MIPS R2000, SUN SPARC, ffiM SystemIR6000 GM-SIMD Processor array IILIAC IV, MPP, CM-I GM-MIMD Multiprocessor All existing tightly coupled (shared-memory)multiprocessors (DEC and ffiM) LM-MIMD Multiple processor TandemVI6,IPSCY2,
Arsitektur Lain
Dalam mesin yon Neumann, program menentukan arus kontrol. Dalam dataflow architecture (arsitektur arus data), sebaliknya, keberadaan data menentukan kapan
mesin akan menjalankan operasi. Model komputasi yang diimplementasikan prosesor
arus data, yang disebut dataflow model (model arus data), adalah pada dasamya
paralel, dan arsitek telah merancang mesin arus data untuk mengimplementasikan
model ini secara efisien. beberapa arsitektur tertentu hanya disebut special-purpose
machine (mesin tujuan khusus) karena fungsi khusus yang mereka jalankan.
Umumnya, menggunakan arsitektur konvensional yang telah dioptirnisasi untuk
aplikasi tertentu Yang termasuk dalam kelompok ini adalah
mesin artificial intelligence, mesin bahasa tingkat tinggi, mesin pemrosesan
tampilan,
prosesor penampil tiga dimensi, dan komputer yang mempunyai kontrol gabung.
