Abstrak
Dibahas algoritma paralel Prefix Sums pada model komputer SIMD dengan model EREW SM SIMD dan model keterhubungan elemen prosesor berbentuk: Khusus, Unshuffle, Pohon dan Mesh dimensi 2. Kompleksitas waktu dari algoritma paralel Prefix Sums adalah:
O(log n) pada model EREW SM SIMD,
O(log n) pada keterhubungan Khusus,
O(log n) pada keterhubungan Unshuffle,
O(log n) I pada keterhubungan Pohon, dan
0(n112) I pada keterhubungan Mesh dimensi 2.
Algoritma paralel Prefix Sums mi dimanfaatkan dalam optimisasi masalah Knapsack.
