Perpustakaan Digital ITB

Komputasi tradisional biasanya menggunakan pendekatan Run-to-Completion. Dengan menggunakan pendekatan ini, akurasi hasil belum dapat ditentukan atau hasilnya belum dapat dinyatakan akurat sebelum semua proses dijalankan dan/atau semua data diproses. Upaya-upaya penelitian yang umumnya dilakukan bertujuan untuk dapat menyelesaikan semua pekerjaan secepat mungkin. Dengan pendekatan ini, komputer mungkin masih diberi beban untuk melakukan pekerjaan yang sebetulnya tidak perlu atau kalaupun dikerjakan tidak memberikan pengaruh terhadap hasil akhirnya. Hal ini membuka peluang pengembangan pendekatan dan strategi komputasi yang memberikan panduan agar komputer hanya melakukan pekerjaan yang diperlukan saja. Dengan demikian, upaya yang dilakukan adalah untuk dapat menyelesaikan pekerjaan yang diperlukan secepat mungkin. Penelitian disertasi ini bertujuan untuk mendapatkan strategi yang dapat meningkatkan kualitas komputasi, yakni tetap dapat memberikan hasil akhir yang benar sesuai tujuan komputasi dengan meminimalkan jumlah operasi yang diperlukan untuk mencapai hasil tersebut. Strategi ini beroperasi pada wilayah perangkat lunak dan diperuntukkan bagi komputasi yang memiliki karakteristik monotonic, bounded, dan permutable. Pendekatan komputasi yang diusulkan disebut dengan Run-to-Decisive. Strategi komputasi yang dikembangkan sebagai manifestasi dari pendekatan Run-toDecisive disebut sebagai Most Significant Operation First – Double Track (MSOFDT). Dengan strategi ini, bagian kalkulasi dan bagian penentuan keputusan ditempatkan di dalam siklus / iterasi utama komputasi. Iterasi berlangsung hingga didapat keputusan yang meyakinkan (tercapai kondisi decisive). Urutan eksekusi elemen-elemen di dalam bagian kalkulasi diatur berdasarkan tingkat signifikansinya. Kondisi decisive diperiksa pada akhir tiap iterasi dengan memanfaatkan konsep double-track, yang mana hasil-antara direpresentasikan dalam bentuk tuple (nilai batas bawah, nilai batas atas). Untuk menangani elemen yang bersifat inkremental, secara garis besar ada enam komponen utama dalam strategi MSOF-DT ini, yakni: 1) penentuan signifikansi, 2) pengurutan elemen komputasi, 3) kalkulasi / eksekusi elemen-elemen komputasi, 4) penghitungan ii batas bawah dan batas atas, 5) penentuan keputusan, serta 6) pemeriksaan kondisi decisive dan deadline. Strategi MSOF-DT telah diterapkan pada beberapa macam kasus permasalahan, yakni: 1) komputasi dengan fungsi kalkulasi Sum-of-Product dan klasifikasi, 2) pengambilan keputusan dengan algoritme Analitic Hierarchy Process, 3) pemeriksaan kemiripan data timeseries berbasis Dynamic Time Warping, 4) logika pengejar dalam Pursuit-Evasion Game, 5) penggunaan bersama dengan teknik lain (paralelisasi dan sampling), dan 6) pengembangan algoritme penjadwalan Sistem Waktu Nyata. Untuk mengukur unjuk kerja penerapan MSOF-DT, digunakan empat metrik, yakni: Trajectory of Accuracy (ToA), Time-to-Decisive Saving (TtDS), produktivitas, dan Trajectory of Accomplished Task (ToAT). Dari hasil percobaan, secara umum dapat disimpulkan bahwa MSOF-DT adalah metode untuk merevisi dan menyempurnakan suatu algoritme komputasi menjadi algoritme lebih efektif bila diterapkan pada sistem komputasi waktu-nyata. Penggunaan strategi MSOF membuat kecepatan peningkatan akurasi hasil (nilai ToA) lebih tinggi dibandingkan tanpa strategi MSOF. Penggunaan MSOF-DT menghasilkan penghematan waktu untuk mencapai kondisi decisive (nilai TtDS) yang lebih besar dibandingkan dengan tanpa MSOF-DT. Semakin besar perbedaan bobot signifikansi antar elemen komputasi, semakin besar pula persentase operasi yang dapat direduksi atau waktu yang dapat dihemat untuk mencapai keputusan yang benar. Produktivitas algoritme yang dimodifikasi menggunakan strategi MSOF-DT lebih besar daripada algoritme aslinya. Untuk pekerjaan yang memiliki deadline, penggunaan MSOF-DT memperbanyak jumlah task yang dapat diselesaikan tanpa melanggar deadline (memberikan nilai ToAT yang lebih baik) daripada yang tanpa MSOF-DT. MSOF-DT bersifat ortogonal terhadap teknik yang lain. Saat digabungkan penggunaannya dengan teknik lain yang sudah ada sebelumnya (misal: teknik paralelisasi dan teknik sampling), MSOF-DT dapat meningkatkan laju peningkatan akurasi dan mempersingkat waktu dalam mencapai keputusan yang benar. Untuk Sistem Waktu Nyata yang deadline-nya mungkin berubah (misal: karena ada interupsi), strategi MSOF-DT dapat membantu meningkatkan nilai ketahanannya (robustness). Strategi MSOF-DT telah dijadikan rujukan dalam menyusun algoritme penjadwalan waktu-nyata yang bernama Earliest Deadline and Shortest Execution Time First / Most Significant Operation First – Run to Decisive (EDSEF/MSOF-DT). Nilai schedulability dari jadwal yang dihasilkan oleh EDSEF/MSOF-DT dapat lebih tinggi daripada jadwal yang dihasilkan oleh algoritme Earliest Deadline First (EDF).