Implementasi Algoritma Branch & Bound Pada Masalah Knapsack

 Metode Branch and Bound

Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi. 

Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).

Teknik Branch and Bound

Ada beberapa teknik dalam Branch and Bound yaitu: 

FIFO Branch and Bound

Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch  and Bound secara First In First Out.

LIFO Branch and Bound

Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.

Least Cost Branch and Bound

Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi. 

Masalah yang dapat dipecahkan with Branch and Bound

Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree :

–Traveling Salesman Problem

–N-Queen Problem

–15 Puzzle Problem

–0/1 Knapsack Problem

–Shortest Path

Knapsack Problem

Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. Penyelesaian masalah dengan menggunakan algoritma exhaustive search adalah mengenumerasikan semua kemungkinan barang-barang yang layak atau memenuhi syarat yaitu tidak melebihi batas daya angkut gerobak untuk dijual setiap harinya , kemudian menghitung tiap-tiap keuntungan yang diperoleh dan memilih solusi yang menghasilkan keuntungan terbesar. 

Berbeda dengan algoritma exhaustive search yang cukup memakan waktu dan dapat menghasilkan solusi yang optimum, penyelesaian masalah dengan menggunakan algoritma greedy dilakukan dengan memasukan objek satu persatu kedalam gerobak dan tiap kali objek tersebut telah dimasukan kedalam gerobak maka objek tersebut tidak dapat lagi dikeluarkan dari gerobak. Pencarian solusi akan dilakukan dengan memilih salah satu jenis greedy (greedy by weight, greedy by profiit or greedy by density) yang diperkirakan dapat menghasilkan solusi yang optimum. Algoritma Branch and Bound juga merupakan salah satu strategi yang dapat digunakan dalam pencarian solusi optimum dari permasalahan knapsack ini.

Algoritma Branch and Bound

Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).

Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :

(i) = (i) + (i)

yang dalam hal ini,

(i) = ongkos untuk simpul i

(i) = ongkos mencapai simpul i dari akar

(i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan)

Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki  minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).

Prinsip dari algoritma branch and bound ini adalah :

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.

2. Jika Q kosong, tidak ada solusi . Stop.

3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai (i) paling kecil. Jika terdapatbeberapa simpul i yang memenuhi, pilih satusecara sembarang.

4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.

5. Untuk setiap anak j dari simpul i, hitung  (j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.

6. Kembali ke langkah 2.

Knapsack Problem Solve

Untuk lebih memahami tahap-tahap penyelesaian permasalahan knapsack ini, kita ambil contoh persoalan seperti yang dituliskan pada bagian Abstrak yaitu dimana seorang pedagang keperluan rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya angkut gerobak yang dimilikinya. Untuk mempermudah

, kita misalkan pedagang keliling tersebut hanya memiliki 4 jenis barang untuk dijual dengan berat dan keuntungan penjualan yang berbeda-beda untuk tiap jenisnya. 

Gerobak yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampuk beban seberat 16 kg. Berikut merupakan tebel penggambaran beratdan keeuntungan yang akan diperoleh untuk tiap penjualan barang tersebut.

dari tiap tiap simpul anak untuk dapat menentukan simpul mana yang kelak akan dibangkitkan yaitu simpul dengan cost tertinggi dalam penelusuran pohon unutk mencapai solusi dari permasalahan ini. Dalam permasalahan ini, kita akan mencari simpul-simpul yang akan membawa kita pada keuntungan terbesar oleh karena itu urutan pembangkitan simpul akan ditentukan oleh simpul mana yang memiliki cost tertinggi. Cost dari tiap simpul akan ditentukan dengan:

(i) = (i) + (i)

yang dalam hal ini,

(i) = cost untuk simpul i

(i) = cost untuk sampai ke simpul I, dalam hal ini merupakan keuntungan dari simpul akar ke simpul i

(i) = cost dari simpul i untuk sampai ke simpul tujuan, dalam hal ini dapat diperoleh dengan menggunakan

BACA JUGA

·         Makalah Sistem Operasi - Application Management

·         Makalah Sistem Operasi - User Management dan Group

·         Makalah Sistem Operasi - Linux Booting

rumus : (P/W)max * daya angkut yang tersisa

pada tahap awal kita akan melakukan perhitungan dengan menggunakan rumus diatas untuk memperoleh batas awal atau akar dari pohon yang juga merupakan simpul pertama. Pada keadaan ini, batas dihitung dengan pemikiran bahwa belum ada satupun barang yang dimasukan kedalam alat pengangkut maka kita dapat memilih 6 sebagai (P/W) terbesar karena belum ada satu barangpun yang dimasukan kedalam alat pengangkut dan kapasitas daya angkutpun masih utuh yaitu seberat 16 kg.

(i) = (i) + (i)

(1) = keuntungan yang diperoleh sampai disimpul

awal + (P/W)max * daya angkut yang tersisa

= 0 + 6 *

= 96

Maka kita memperoleh 96 batas awal atau cost dari simpul awal.

Bangkitkan simpul-simpul anak dari akar pohon yaitu dengan membangkitkan simpul 1, simpul 2, simpul 3 dan simpul 4 sebagai gambaran dari 4 pilihan barang yang akan dimasukan pertama kali pada alat pengangkut dengan x1 merupakan keuntungan yang akan diperoleh pada penjualan tiap barang tersebut. Kemudian kita akan menghitung cost dari tiap simpul anak yang hidup dan juga kelayakannya untuk tetap hidup atau harus dibunuh. Dalam hal ini, simpul yang jumlah dari lintasannya tidak bisa lagi dibangkitkan (jika ditambah barang lagi kedalam alat pengangkut maka beratnya akan melebihi daya angkut) akan dibunuh.

(2) = 12 + 5*(16-2) = 82

(3) = 15 + 6*(16-5) = 81

(3) = 50 + 6*(16-10)=86

(4) = 10 + 6*(16-5)=76

Dari simpul-simpul yang telah dibangkitkan dan dihitung cost nya, maka diperoleh bahwa simpul 4 lah yang memiliki cost tertinggi oleh karena itu maka simpul 4 akan di perluas lagi. Simpul 6 ,7,8 akan dibangkitkan sebagai perluasan dari simpul 4 dengan barang yang mungkin dimasukan kedalam alat pengangkut adalah barang ke 1,2 dan 4. kemudian kita akan mengkitung cost dari simpul 6,7dan 8.

(6) = (50+12) + 3*(16-10-2) = 74

(7) = (50+15) + 6*(16-10-5) = 71

(8) = (50+10) + 6*(16-10-5) = 66

 Implementasi Algoritma Divide and Conquer

Nama   : Fikih Yuhada Sena

NPM    : 20312060

Kelas    : IF 20B

Algoritma Divide and Conquer adalah algoritma yang sangat populer pada di dunia ilmu komputer. Algoritma Divide and Conquer adalah algoritma yang memiliki prinsip untuk membagi-bagi permasalahan yang terlalu besar menjadi beberapa atau sub-masalah yang lebih kecil sehingga menjadi mudah untuk diselesaikan. sub-sub masalah yang telah dibagi menjadi beberapa bagian yang lebih kecil kemudian akan dicari solusinya, setelah mendapatkan solusinya, solusi dari sub-sub masalah tersebut akan digabung menjadi satu untuk menyelesaikan masalah awal atau masalah utama. 

Algoritma Sorting atau algoritma pengurutan adalah suatu langkah yang sistematis dan berurutan. atau algoritma untuk meletakkan kumpulan data ke dalam suatu urutan tertentu berdasarkan satu atau beberapa "kunci" pada tiap-tiap elemen.

Algoritma Searching atau algoritma pencarian adalah algoritma yang menerima suatu argumen "kunci" dan dengan menggunakan suatu langkah-langkah tertentu akan mencari "kunci" tersebut. Setelah proses pencarian dilakukan, akan diperoleh salah satu dari dua kemungkinan, yaitu data berhasil ditemukan, atau data tidak ditemukan.

Divide and Conquer Pada Sorting

1. Selection Sort

Selection Sort adalah sebuah teknik pengurutan dengan cara mencari nilai tertinggi / terendah pada suatu kumpulan data (array) kemudian menempatkan nilai tersebut pada tempatnya. Algoritma ini dibagi menjadi dua berdasarkan urutan datanya, yaitu : dari kecil ke besar (Ascending), dan dari besar ke kecil (Descending). Algoritma ini pada dasarnya memilih nilai yang terbesar/terkecil, dan menukarkan nilai tersebut dengan nilai disebelah kiri/kanan pada data. Dan kemudian langkah tersebut diulang secara terus menerus hingga data tersusun. Algoritma ini tidak efektif bila digunakan pada array yang jumlah nya besar karena kompleksitas dari algoritma ini adalah O(x2) dimana n adalah jumlah item.

2. Insertion Sort

Algoritma Insertion Sort adalah sebuah teknik pengurutan dengan cara membandingkan dan mengurutkan dua data pertama pada suatu kumpulan data (array). Algoritma ini pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, data yang belum diurutkan, dan data yang sudah diurutkan. Elemen data pertama diambil dari bagian data yang belum diurutkan dan diletakkan pada posisinya di bagian data yang telah diurutkan. Algoritma ini dapat mengurutkan data secara ascending dan descending. Algoritma ini tidak efektif bila digunakan pada array dengan jumlah besar, karena kompleksitas algoritma ini adalah O() dimana n adalah jumlah item.

3. Quick Sort

Algoritma Quick Sort adalah salah satu algoritma pengurutan data, algoritma ini menggunakan teknik pemecahan data menjadi beberapa bagian atau partisi, sehingga algoritma ini disebut juga dengan nama partition exchange sort. 

Algoritma ini mengambil salah satu elemen pada suatu data secara acak (tengah) yang disebut dengan pivot lalu menyimpan semua elemen yang lebih kecil disebelah kiri pivot dan elemen yang lebih besar pada sebelah kanan pivot. Langkah tersebut dilakukan secara berulang sampai semua elemen menjadi terurut.

Divide and Conquer Pada Searching

1. Binary Search

Algoritma Binary Search atau algoritma pencarian Biner, salah satu teknik pencarian yang dilakukan secara berulang kali  membagi setengah dari jumlah data yang dicari sehingga dapat memperkecil lokasi pencarian. Dengan begitu dapat mempercepat waktu pencarian. Jika ditemukan kecocokan pada suatu data dengan data yang dicari maka pencarian akan selesai, jika tidak, pencarian akan terus dilakukan hingga akhir dari bagian data tersebut. Algoritma ini cocok untuk mencari pada jumlah data yang banyak, karena kompleksitas algoritma ini adalah O(log n) dimana n adalah jumlah item. Tetapi sebelum menggunakan algoritma ini, pastikan data sudah terurut. Jika tidak maka pencarian tidak bisa dilakukan.

2. Linear Search

Algoritma Linear Search atau pencarian linear, adalah salah satu teknik dari pencarian data, teknik ini mencari data dengan mengecek semua data secara satu per satu. Apabila ditemukan kecocokan pada data dengan data yang dicari, maka pencarian akan selesai. Jika tidak, pencarian akan terus dilakukan hingga data terakhir. Algoritma ini tidak efektif jika digunakan pada data yang besar karena kompleksitas algoritma ini adalah O(n) dimana n adalah jumlah item. Dan jika data yang dicari berada pada bagian paling akhir dari kumpulan data tersebut (array), maka pencarian tetap harus dilakukan dari yang paling awal, sehingga membutuhkan waktu yang lama.

 ALGORITMA DIVIDE AND CONQUER

Pengertian 

Algoritma Divide dan Conquer merupakan hasil gabungan dari kata Divide dan Conquer. Conquer ini berarti membagi persoalan menjadi beberapa masalah yang memiliki kemiripan dengan persoalan semula namun berbeda kecil. Sedangkan Conquer merupakan penyelesaian setiap masalah yang ada. Pengertian dari Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar menjadi beberapa bagian yang lebih kecil secara rekrusif sehingga masalah tersebut dapat terpecahkan langsung.

Sejarah

Nama Divide and Conquer sendiri diambil dari siasat militer milik Belanda pada zaman penjajahan dengan nama divide ut imperes. Strategi ini merupakan strategi yang fundamental dalam ilmu komputer dengan sebutan Divide and Conquer. Algoritma ini ditemukan ilmuwan Rusian bernama Anatolii Alexeevich Karatsuba pada tahun 1960.

Cara Kerja

Ada 3 cara tahap kerja pada algoritma ini, yaitu :

Divide : Membagi masalah menjadi beberapa upa-masalah yang memilki kemiripan dengan masalah semula namun berukuran lebih kecil.

Conquer : Memecahkan masing - masing upa-masalah secara rekrusif.

Conbine : Menggabungkan solusi masing - masing upa-masalah sehingga membentuk masalah semula.

Source :

 https://creatormedia.my.id/rangkuman-algoritma-divide-and-conquer/

https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2020-2021/Algoritma-Divide-and-Conquer-(2021)-Bagian1.pdf 

https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2014-2015/Makalah2015/Makalah_IF221_Strategi_Algoritma_2015_078.pdf#:~:text=Pada%20zaman%20dahulu%2C%20divide%20and%20conquer%20merupakan%20strategi,untuk%20mengalikan%20dua%20buah%20bilangan%20bulat%20yang%20besar.

 Tentang Pembuat : 

Nama    : Fikih Yuhada Sena

NPM     : 20312060

Kelas     : IF 20 B

LINK WEBSITE :

Universitas Teknokrat Indonesia

https://ftik.teknokrat.ac.id/

Permasalahan numerik dan cara menyelesaikannya

Nama : Fikih Yuhada Sena

NPM    : 20312060

Kelas   : IF 20 B

Sorting

Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

1. Urut naik (ascending)
   Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

2. Urut turun (descending)

   Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Sorting merupakan suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting:

1. Urut naik (ascending)
   Mengurutkan dari data yang mempunyai nilai paling kecil sampai paling besar

2. Urut turun (descending)

   Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Permasalahan :

Urutkan 5,2,1,7,9,4,3 dari kecil ke besar

Penyelesaian :

Menggunakan metode bubble sort

5,2,1,7,9,4,3 Tukar

2,5,1,7,9,4,3 Tukar

2,1,5,7,9,4,3 Tidak ditukar karena 5 lebih kecil dari 7

2,1,5,7,9,4,3 Tidak ditukar karena 7 lebih kecil dari 9

2,1,5,7,4,9,3 Tukar

2,1,5,7,4,3,9 Tukar, setalah seperti ini maka program akan mengulang

1,2,5,7,4,3,9 Tukar

1,2,5,7,4,3,9 Tidak ditukar karena 2 lebih kecil dari 5

1,2,5,4,7,3,9 Tukar

1,2,5,4,3,7,9 Tukar, lalu diulang kembali

1,2,5,4,3,7,9 Tidak ditukar karena urutanya sudah sesuai

1,2,5,4,3,7,9 Tidak ditukar karena 2 lebih kecil dari 5

1,2,4,5,3,7,9 Tukar

1,2,4,3,5,7,9 Tukar

1,2,4,3,5,7,9 Tidak ditukar karena 5 lebih kecil dari 7

1,2,4,3,5,7,9 Tidak ditukar karena sudah sesuai urutan,selanjutnya diulang lagi

1,2,4,3,5,7,9 Tidak ditukar karena 1,2 sudah sesuai urutanya

1,2,4,3,5,7,9 Tidak ditukar karena 2 lebih kecil dari 4

1,2,3,4,5,7,9 Tukar

Maka terbentuk hasil dari bubble sort 1,2,3,4,5,7,9

Kelebihan dan kekurangan :

Merupakan metode yang paling simpel dan metode pengurutan yang paling tidak efisien. Pada saat pengurutan data yang sangat besar akan mengalami kelambatan yang luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan.

Searching

Permasalahan :

Selaikan gambar berikut ini dengan search problem BFS

Penyelesaian :

Dari gambar di atas urutanya dari kiri ke kanan. Setelah sampai di tahap akhir maka

Kita anggap kotak yang dihitamkan tidak ada nilainya, sebenarnya ini seperti kita bermain rubrik. Saya akan menjelaskan dari paling bawah, setelah terbentuk 2,3,0 pada kolom pertama, dan kolom ke 2. 1,8,4, dan kolom ke 3. 7,6,5. Untuk menjadi bilangan yang dapat diselesaikan maka kita harus menguruttkanya menjadi :

1 2 3

8 0 4

7 6 5

Dengan cara memindahkannya dengan posisi yang berurut

Kelebihan dan kekurangan BFS :

tidak akan menemukan jalan buntu dan kelemahannya membutuhkan waktu yang cukup lama, karena akan menguji tiap n level untuk menemukan atau mendapatkan solusi pada level yang ke-(n-1)

String processing

Permasalahan :

Misalkan tersedia koin : 1, 3, 5.

Uang senilai X=8 dapat di tukar dengan cara algoritma greedy :

Penyelesaian :

1+1+1+1+1+1+1+1 = 8 (8 koin)

1+1+1+1+1+3=8 (6 koin)

1+1+1+5=8 (4 koin)

1+1+3+3=8 (4 koin)

3+5=8 (2 koin) solusi optimal.

Kelebihan dan kelemahan algoritma greedy :

Kelebihan dari algoritam greedy adalah cepat dalam bertindak alias fast response.Kelemahan dari algoritma greedy memiliki berupa hasil akhirnyayang tidak sebaik algoritma brute force.

Perbedaan Proses dan Thread | The Difference between a Process and a Threads

Nama : Fikih yuhada sena

Kelas : IF 20B

Fakultas : FTIK

Assalamualaikum Wr. Wb saya disini ini menjelaskan materi tentang Perbedaan Proses dan Thread | The Difference between a Process and a Threads .sebagai berikut :

1. Pengertian Proses

Sebuah proses, secara umum, adalah serangkaian terus menerus dari tindakan untuk mencapai hasil yang spesifik. Namun, dalam dunia komputer, proses adalah sebuah contoh dari mengeksekusi program komputer. Dengan kata lain, itu adalah konsep dari kejadian tunggal dari program komputer yang berjalan.
Berdasarkan jumlah thread yang telibat dalam proses, proses dapat dibedakan menjadi 2 jenis yaitu :

• proses tunggal-thread : proses yang hanya memiliki satu thread
• proses multi-thread : Proses yang memiliki lebih dari satu thread

2. Pengertian Thread

thread adalah pelaksanaan instruksi terkecil dari program komputer yang dapat dikelola secara independen sesuai dengan jadwal. Sebuah thread adalah jalan eksekusi sederhana dalam proses. Sebuah thread adalah sebagai proses kuat karena thread bisa melakukan proses apa saja yang bisa dilakukan. Sebuah thread adalah proses ringan dan membutuhkan sumber daya yang lebih sedikit. Thread dapat mulai dari membaca dan menulis ke variabel yang sama dan struktur data variabel. Thread dapat berkomunikasi antara thread dengan mudah.

3. Perbedaan Proses dan Thread

a. PROSES

• Proses mencakup program counter, yaitu sebuah stack untuk menyimpan alamat dari instruksi yang selanjutnya akan di eksekusi dan di registrasi.
• Memiliki ruang alamat atau IP address masing-masing.
• Dari satu proses dengan proses lainnya harus menggunakan komunikasi.
• Memiliki overhead.
• Hanya dapat mengendalikan proses turunannya.
• Perubahan pada parent proses tidak mempengaruhi proses turunannya.
• Pembentukan proses membutuhkan waktu yang lebih lama.
• Waktu yang dibutuhkan untuk mengakhiri proses lebih lama.

b. THREAD

• Merupakan unit dasar dari penggunaan CPU dan sering disebut dengan lightweight process.
• Ruang alamat atau IP address digunakan secara bersama-sama dari proses yang menciptakannya.
• Memiliki akses langsung ke segmen data dari prosesnya.
• Dapat saling berkomunikasi dengan thread lain dalam satu proses.
• Hampir tidak memiliki overhead.
• Perubahan pada thread utama seperti pembatalan atau perubahan prioritas dapat mempengaruhi tingkah laku thread lain dalam satu proses.
• Pembentukan thread membutuhkan waktu yang lebih sedikit.
• Waktu yang dibutuhkan untuk mengakhiri thread lebih sedikit.
• Lebih mudah dan cepat melakukan swicth antar thread daripada switch antar proses.

Pengertian, Sejarah, Keuntungan, Kekurangan, SIMD

1. Pengertian  SIMD

SIMD adalah kelas komputer paralel dalam taksonomi Flynn. Klarifikasi diperlukan Ini menjelaskan komputer dengan beberapa elemen pemrosesan yang melakukan operasi yang sama pada beberapa titik data secara bersamaan. Mesin semacam itu mengeksploitasi paralelisme tingkat data , tetapi bukan konkurensi : ada komputasi simultan (paralel), tetapi hanya satu proses (instruksi) pada saat tertentu. SIMD khususnya dapat diterapkan untuk tugas-tugas umum seperti mengatur kontras dalam gambar digital atau mengatur volume audio digital . Paling modernDesain CPU menyertakan instruksi SIMD untuk meningkatkan kinerja penggunaan multimedia . SIMD tidak sama dengan SIMT , yang menggunakan utas .

2. Keuntungan SIMD

Aplikasi yang dapat memanfaatkan SIMD adalah aplikasi di mana nilai yang sama ditambahkan ke (atau dikurangi dari) sejumlah besar titik data, operasi umum pada banyak aplikasi multimedia . Salah satu contohnya adalah mengubah kecerahan gambar. Setiap piksel gambar terdiri dari tiga nilai kecerahan bagian warna merah (R), hijau (G), dan biru (B). Untuk mengubah kecerahan, nilai R, G dan B dibaca dari memori, nilai ditambahkan ke (atau dikurangkan dari) nilai tersebut, dan nilai yang dihasilkan ditulis kembali ke memori.

Dengan prosesor SIMD ada dua peningkatan pada proses ini. Untuk satu data dipahami sebagai blok, dan sejumlah nilai dapat dimuat sekaligus. Alih-alih serangkaian instruksi yang mengatakan "ambil piksel ini, sekarang ambil piksel berikutnya", prosesor SIMD akan memiliki instruksi tunggal yang secara efektif mengatakan "ambil n piksel" (di mana n adalah angka yang bervariasi dari desain ke desain). Untuk berbagai alasan, ini bisa memakan waktu lebih sedikit daripada mengambil setiap piksel satu per satu, seperti pada desain CPU tradisional.

Keuntungan lainnya adalah bahwa instruksi beroperasi pada semua data yang dimuat dalam satu operasi. Dengan kata lain, jika sistem SIMD bekerja dengan memuat delapan titik data sekaligus, addoperasi yang diterapkan ke data tersebut akan terjadi pada kedelapan nilai pada saat yang bersamaan. Paralelisme ini terpisah dari paralelisme yang disediakan oleh prosesor superscalar ; delapan nilai diproses secara paralel bahkan pada prosesor non-superskalar, dan prosesor superskalar mungkin dapat melakukan beberapa operasi SIMD secara paralel.

3. Kekurangan SIMD

• Tidak semua algoritme dapat divektorisasi dengan mudah. Misalnya, tugas berat kontrol aliran seperti penguraian kode mungkin tidak dengan mudah mendapatkan keuntungan dari SIMD; namun, secara teori dimungkinkan untuk melakukan vektorisasi perbandingan dan "aliran batch" untuk menargetkan optimalitas cache maksimal, meskipun teknik ini akan memerlukan lebih banyak status perantara. Catatan: Sistem pipeline batch (contoh: GPU atau pipeline rasterization software) paling menguntungkan untuk kontrol cache saat diimplementasikan dengan intrinsik SIMD, tetapi tidak eksklusif untuk fitur SIMD. Kompleksitas lebih lanjut mungkin terlihat untuk menghindari ketergantungan dalam rangkaian seperti string kode; sedangkan independensi diperlukan untuk vektorisasi.
• File register besar yang meningkatkan konsumsi daya dan area chip yang dibutuhkan.
• Saat ini, mengimplementasikan algoritma dengan instruksi SIMD biasanya membutuhkan tenaga manusia; sebagian besar kompiler tidak menghasilkan instruksi SIMD dari program C biasa , misalnya. Vektorisasi otomatis dalam kompiler adalah area aktif penelitian ilmu komputer. (Bandingkan pemrosesan vektor .)
• Pemrograman dengan set instruksi SIMD tertentu dapat melibatkan banyak tantangan tingkat rendah.
  1. SIMD mungkin memiliki batasan pada penyelarasan data ; programmer yang akrab dengan satu arsitektur tertentu mungkin tidak mengharapkan ini.
  2. Mengumpulkan data ke register SIMD dan menyebarkannya ke lokasi tujuan yang benar itu rumit (terkadang membutuhkan operasi permute) dan bisa jadi tidak efisien.
  3. Instruksi khusus seperti rotasi atau penambahan tiga operan tidak tersedia di beberapa set instruksi SIMD.
  4. Set instruksi khusus untuk arsitektur: beberapa prosesor tidak memiliki instruksi SIMD sama sekali, jadi programmer harus menyediakan implementasi non-vektorisasi (atau implementasi vektorisasi yang berbeda) untuk mereka.
  5. Arsitektur yang berbeda menyediakan ukuran register yang berbeda (misalnya 64, 128, 256 dan 512 bit) dan set instruksi, yang berarti bahwa pemrogram harus menyediakan banyak implementasi kode vektor untuk beroperasi secara optimal pada CPU tertentu. Selain itu, set instruksi SIMD yang mungkin bertambah dengan setiap ukuran register baru.
  6. Set instruksi MMX awal berbagi file register dengan stack floating-point, yang menyebabkan inefisiensi saat mencampur floating-point dan kode MMX. Namun, SSE2 memperbaikinya.

Untuk memperbaiki masalah 1 dan 5, ekstensi vektor RISC-V dan ARM's Scalable Vector Extension menggunakan pendekatan alternatif: alih-alih memaparkan detail tingkat sub-register kepada programmer, set instruksi mengabstraksikannya sebagai beberapa "register vektor "yang menggunakan antarmuka yang sama di semua CPU dengan set instruksi ini. Perangkat keras menangani semua masalah penyelarasan dan "strip-mining" loop. Mesin dengan ukuran vektor berbeda akan dapat menjalankan kode yang sama. ^[6] LLVM menyebut jenis vektor ini "vscale".

Sejarah dan Perkembangan Random Access Memory (RAM)

A. RAM

RAM adalah singkatan dari Random Access Memory. Sebuah bagian dari sistem komputer yang sangat penting. Tidak hanya pada komputer PC maupun notebook saja yang membutuhkan RAM, PDA dan banyak perangkat elektronik lain pun ikut membutuhkan bagian ini.

Dan untuk setiap peralatan memiliki tingkat kebutuhan yang berbeda-beda. Misalkan saja sebuah komputer yang masih menggunakan operating system lama contohnya Windows 98, maka RAM yang dibutuhkan tidak akan sebesar komputer yang menggunakan Windows XP sebagai operating system-nya.

Selain operating system, aplikasi yang dijalankan pun sangat bergantung kepada RAM. Semakin berat aplikasi yang akan dijalankan, maka bobot RAM akan semakin besar. Karena pada RAM-lah untuk sementara aplikasi atau data yang tengah Anda akses tersimpan.

Sedangkan untuk membeli sebuah RAM, bukan bobot saja yang akan menjadi pertimbangan utama. Tapi juga ada aspek lain yang tidak kalah pentingnya harus ikut dipikirkan. Seperti kecepatan, tipe, jenis soket, dan motherboard yang digunakan.

Karena saat ini, selain setiap aplikasi memiliki kebutuhan sistem yang berbeda-beda, kehadiran RAM pun sudah sangat beragam. Sedangkan harganya semakin hari semakin terjangkau. Teknologi yang ada pada RAM pun terus berkembang. Mulai ditemukannya DDR, sistem dual-channel,DDR2,dll.

Belum lagi kecepatannya yang juga semakin lama semakin cepat. Dari hanya 66 MHz sampai kini telah mencapai 600 MHz. Begitu pula dengan kapasitas. Sepuluh tahun yang lalu RAM 8 MB masih sangat mudah ditemukan, tetapi sekarang RAM ini sangat sulit ditemui. Para penjual perangkat komputer lebih banyak menawarkan RAM dengan memory minimal 128 MB per kepingnya. Betapa langkah yang sangat jauh telah dilalui RAM dalam perkembangannya.

B. PERKEMBANGAN

1. Pada tahun 1987, RAM jenis FPM (Fast Page Mode) diperkenalkan. FPM merupakan bentuk RAM yang paling kerap digunakan dalam system komputer pada masa itu. FPM juga turut dikenali sebagai DRAM (Dynamic Random Access Memory) sahaja. FPM menggunakan modul memori SIMM (Single Inline Memory Module) 30 pin dan SIMM 72 pin.

2. Pada tahun 1995, perkembangan teknologi maklumat telah menghasilkan modul memori yang seterusnya yaitu EDO (Extended Data Out). EDO mirip dengan FPM, cuma ia diubah sedikit untuk membolehkan akses memori berturutan berlaku dengan labih pantas. Ini bermakna ‘pengawal memori’ boleh menjimatkan masa dengan mengurangkan beberapa langkah dalam proses pengalamatan (addressing). EDO juga membolehkan CPU mengakses memori 10% hingga 15% lebih pantas berbanding dengan FPM.

3. Pada tahun 1997, SDRAM diperkenalkan, dengan clock speed (kecepatan putaran) 66 MHz, SDRAM ini mampu menghantarkan data dengan kecepatan maksimal 533 MB/det. Lalu seiring dengan clock speed yang bertambah kencang, kecepatan pengantaran datapun menjadi semakin cepat.Untuk SDRAM dengan clock speed 133 MHz, data yang dihantarkan dapat mencapai 1,066 GB/det.

4. Pada tahun 1999, RDRAM diperkenalkan, RDRAM lebih banyak ditujukan untuk atau user lain yang memang sangat membutukan memory berkecepatan tinggi.Kualitas yang dimiliki oleh RDRAM mengakibatkan harganya sangat tinggi. Dan untuk mencarinya pun tidak semudah SDRAM atau DDR. RDRAM menggunakan modul yang disebut RIMM. Berbeda dengan modul yang dimiliki SRAM atau DDR yang menggunakan transfer data secara paralel pada data bus 64-bit. RDRAM menggunakan transfer data secara serial pada data bus 16-bit.RDRAM yang paling umum digunakan adalah RDRAM yang memiliki kecepatan 1,6 GB/det. 

RDRAM ini lebih dikenal dengan sebutan RIMM1600.Sedangkan RDRAM yang menggunakan data bus 16-bit saat ini sudah dapat mencapai kecepatan 2,4 GB/det (RIMM2400).Sedangkan untuk jenisnya, RDRAM ada dua macam yang pertama adalah yang bekerja pada data bus 16-bit dan yang kedua adalah RDRAM yang bekerja pada data bus 32-bit. Jika RDRAM yang bekerja pada data bus 16-bit memiliki jumlah pin sebanyak 184 pin dan diperuntukkan untuk sistem single-channel, maka RDRAM yang bekerja pada data bus 32-bit memiliki jumlah pin sebanyak 242 pin, dan diperuntukkan bagi sistem dual-channel. Serta satu lagi yang menjadi ciri khas dari RDRAM adalah adanya fasilitas yang dapat menjaga agar memory tidak panas.Sebenarnya dari performa mungkin tidak jauh berbeda, namun untuk beberapa sistem menggunakan RDRAM akan sangat mendukung terlebih lagi server. Oleh sebab itu, yang paling banyak menggunakan RDRAM adalah server.

5. Pada tahun 2000, DDR-SDRAM diperkenalkan. RAM ini merupakan inovasi daripada SDRAM di mana ia menjanjikan DDR yang kali pertama muncul, memang memiliki clock speed yang sama dengan SDRAM yaitu 100 MHz, tetapi meskipun sama kecepatan pengantaran datanya jauh lebih besar DDR. Hal ini disebabkan dalam satu putarannya DDR melakukan sekaligus dua pekerjaan (pengoperasionalan). Berbeda pada SDRAM yang hanya melakukan satu pengoperasionalan. Hasilnya: pada DDR dengan clock speed 100 MHz, data yang dihasilkan dapat mencapai 2,1 GB/det. Nilai inilah yang menjadi alasan mengapa DDR ini disebut DDR dengan tipe PC2100.

Sampai saat ini, nilai maksimal yang diakui oleh The JEDEC Solid State Technology Association, sebuah asosiasi yang bertanggung jawab tentang standar memory ini adalah nilai yang dimiliki oleh DDR400 PC3200, yaitu 3,2 GB/det. Padahal saat ini ada beberapa produsen RAM yang menawarkan RAM dengan kecepatan yang jauh lebih besar lagi. Seperti Corsair, Kingston, Mushkin, dan beberapa produsen lainnya sudah ada yang berani menawarkan DDR dengan tipe PC3700 dan PC4000 yang masing-masing sanggup menghantarkan data dengan kecepatan 3,7 GB/det dan 4 GB/det. Sayangnya, DDR ini masih sulit dicari di pasaran, khususnya di Indonesia.

DDR dengan kecepatan tinggi tersebut sangat cocok digunakan untuk kebutuhan-kebutuhan para gamers dan untuk para pengguna yang sangat sering menggunakan sistem overclock. Karena DDR dengan kecepatan tinggi ini mampu menangani pengoperasian yang membutuhkan panas tinggi, seperti penerapan overclocking.

6. Pada tahun 2004 di perkenalkanlah DDR2 SDRAM, Energi: DDR2 membutuhkan energi setengah lebih kecil dari energi yang dibutuhkan DDR biasa beroperasi, sehingga dapat mengurangi panas pada komputer. Apalagi pada notebook yang secara otomatis juga akan lebih menghemat baterai.

High clock speed: DDR2 menggunakan clock speed awal sebesar 400 MHz. Nilai ini juga masih bisa di tingkatkan menjadi 800 MHz. Ketahanan: Dengan DDR2, Anda dapat memiliki satu keeping 2 GB dan dipasangkan pada single bank module.

Karena daya tahan DDR2 masih lebih baik dari DDR biasa.

* Ukuran: Dari segi ukuran, DDR2 juga masih lebih kecil dibandingkan DDR biasa.

* Teknologi koneksi: DDR2 menggunakan teknologi koneksi yang dinamakan Ball Grid Array (BGA), yang belum digunakan pada DDR biasa.

7. Pada tahun 2007 hingga sekarang muncul DDR3 SRAM. Memori jenis ini memiliki kebutuhan daya yang berkurang sekitar 16% dibanding DDR2. Hal ini disebabkan memori jenis ini memakai teknologi 90 nm sehingga hanya membutuhkan tegangan 1.5 volt saja. Memori ini memiliki kecepatan yang baik dibanding memori – memori generasi awal.

8. Dual Core adalah penggunaan dua buah inti (core) prosesor dalam sebuah kemasan prosesor konvensional. Dual core (inti prosesor) ditempatkan pada sebuah CPU untuk meningkatkan kinerjanya. Setiap core ini tidak lebih cepat dibanding CPU biasa dengan clockspeed yang sama, tetapi semua proses perhitungan dibagi kepada 2 inti prosesor tersebut.

Logikanya, menggunakan prosesor multi-core akan mempercepat perhitungan algoritma yang dikerjakan sebuah sistem PC. Diibaratkan, berpikir sebuah pekerjaan dengan menggunakan dua otak, tentunya pekerjaan itu akan lebih cepat selesai. Produsen prosesor terkemuka di dunia (Intel dan AMD), mengembangkan teknologi dual core ini karena tuntutan aplikasi-aplikasi yang semakin tinggi atas prosesor yang memiliki tingkat komputasi yang tinggi. Karena pengembangan prosesor dengan menggunakan satu inti sudah mulai stagnan, maka mulai dikembangkan prosesor yang memiliki inti prosesor lebih dari satu.

9. CORE 2 DUO Pada tahun 2006 di luncurkanlah Intel Core 2 Duo yang pertama diberi kode nama Conroe. Processor ini dibangun dengan menggunakan teknologi 65 nm dan ditujukan untuk penggunaan desktop menggantikan jajaran Pentium 4 dan Pentium D. Bahkan pihak Intel mengklaim bahwa Conroe mempunyai performa 40% lebih baik dibandingkan dengan Pentium D yang tentunya sudah menggunakan dual core juga. Core 2 Duo hanya membutuhkan daya yang lebih kecil 40% dibandingkan dengan Pentium D untuk menghasilkan performa yang sudah disebutkan di atas.

Processor yang sudah menggunakan core Conroe diberi label dengan “E6×00”. Beberapa jenis Conroe yang sudah beredar di pasaran adalah tipe E6300 dengan clock speed sebesar1.86 GHz, tipe E6400 dengan clock speed sebesar 2.13 GHz, tipe E6600 dengan clock speed sebesar 2.4 GHz, dan tipe E6700 dengan clock speed sebesar 2.67 GHz. Untuk processor dengan tipe E6300 dan E6400 mempunyai Shared L2 Cache sebesar 2 MB, sedangkan tipe yang lainnya mempunyai L2 cache sebesar 4 MB. Jajaran dari processor ini memiliki FSB (Front Side BUS) sebesar 1066 MT/s (Megatransfer) dan daya yang dibutuhkan hanya sebesar 65 Watt TDP (Thermal Design Power).