PICHAFF² - Pemecah SAT Paralel Hierarkis

Abstrak

Kami menyajikan prosedur SAT terdistribusi hierarkis untuk mikrokontroler PIC Microchip. Algoritme ini merupakan adaptasi dari pemecah mutakhir CHAFF yang dioptimalkan untuk sumber daya terbatas dari prosesor Microchip. Lingkungan perangkat keras yang mendasarinya adalah sistem multiprosesor khusus yang berbasis kartu slot ISA PC, yang masing-masing dapat menampung hingga 9 mikrokontroler PIC. Kami mengusulkan skema pencurian kerja baru yang mampu mengelola beberapa kartu multiprosesor ini secara paralel. Selain membahas aspek teknis, kami juga menunjukkan efisiensi pendekatan kami melalui serangkaian eksperimen.

Pendahuluan

Masalah NP-complete dalam membuktikan bahwa formula Boolean proposisional dapat dipenuhi (SAT) adalah salah satu masalah fundamental dalam ilmu komputer. Banyak masalah dapat diubah menjadi masalah SAT sedemikian rupa sehingga solusi dari masalah SAT juga merupakan solusi dari masalah asli yang bersangkutan. Banyak perkembangan dalam menciptakan algoritme SAT yang kuat telah dibuat dalam beberapa tahun terakhir: SATO [11], GRASP [8], atau CHAFF [9] misalnya, yang semuanya didasarkan pada metode Davis-Putnam klasik yang diperkenalkan pada awal 1960-an [5]. Algoritme-algoritme ini telah berhasil diterapkan pada masalah dunia nyata di bidang model checking, equivalence checking, atau timing analysis, untuk menyebutkan beberapa di antaranya.