Tugas Arsitektur Komputer Lanjut Nama : Dedi triyanto NIM : 23205043 Soal 1.1 Penyelesaian : Integer arithmetic 45000 x 1 Data transfer 32000 x 2 Floating point 15000 x 2 Control transfer 8000 x 2 Total (C) CPI =
= 45000 = 64000 = 30000 = 16000 + 155000
C 155000 = = 1,55 Ic 100000
MIPS rate =
f 40 x10 6 = = 25,8 MIPS 1,55 x10 6 CPIx10 6
T = Ic x CPI x τ =
IcxCPI 100000 x1,55 = = 3,875 ms f 40 x10 6
Soal 2.1 Penyelesaian : (a) Computational granularity Adalah suatu ukuran dari sejumlah perhitungan yang rumit pada suatu proses software. Ukuran paling sederhana adalah menghitung jumlah instruksi pada suatu grain (program segment). (b) Communication latency Untuk poin (c), (d), dan (e): S1: Load R1, A /R1 Memory(A)/ S2: Add R2, R1 /R2 (R1) + (R2) S3: Move R1, R3 /R1 (R3)/ S4: Store B, R1 /Memory(B) (R1) (c) Flow dependence Statemen S2 adalah flow dependence pada statemen S1 jika urutan pengambilan eksekusi terjadi dari S1 ke S2 dan jika sedikitnya 1 output dari s1 diumpankan sebagai input pada S2. Pada contoh di atas S2 flow dependence pada S1 karena variabel memory(A) harus melewati register R1.
(d) Antidependence Statemen S3 adalah antidependence pada statemen S2 jika S3 mengikuti S2 pada urutan program dan jika output dari S3 bersamaan waktunya dengan input S2. Pada contoh di atas S3 antidependence pada S2 karena adanya potensi konflik pada isi register di R1. (e) Output dependence 2 statemen adalah outout dependence jika mereka menghasilkan (write) variabel output yang sama. Pada contoh di atas S3 adalah output dependence pada S1 karena keduanya mengubah register yang sama yaitu R1. (f) I/O dependence Terjadi karena file yang sama di rujuk oleh 2 I/O statement. S1: Read(4), A(I) /Read array A from tape unit 4/ S2: Rewind(4) /Rewind tape unit 4/ S3: Write(4), B(I) /Write array B into tape unit 4/ S4: Rewind(4) /Rewind tape unit 4/ S1 dan S3 adalah I/O dependence satu dengan yang lain karena keduanya mengakses file yang sama dari tape unit 4. (g) Control dependence Ini berkenaan pada situasi dimana perintah eksekusi dari statemen tidak dapat ditentukan sebelum run time. Contohnya, kondisi statemen IF (pada Fortran) tidak akan diubah sampai run time. Do 10 I = 1, N IF (A(I – 1) .EQ. 0) A(I) = 0 10 Continue (h) Resource dependence Adalah yang menyangkut dengan conflik pada penggunaan shared recources,- seperti unit integer, unit floating point, register, dan wilayah memori,- diantara parallel event. (i) Bernstein conditions Adalah suatu set kondisi berdasarkan dimana 2 proses dapat di eksekusi secara parallel. (j) Degree of parallelism Adalah jumlah prosesor yang digunakan untuk mengeksekusi suatu program untuk tiap priode waktu.
Soal 3.1 Penyelesaian : (a) 4 prosesor f1, f2, f3, f4 : f1: Arithmetic and logic 1 f2: Load/store with cache hit 2 f3: Branch 4 f4: Memory reference with cache miss untuk f1: C 33.000 CPI = = = 0,6 Ic 55.000 untuk f2: C 19.800 CPI = = = 0,36 Ic 55.000 untuk f3: C 26.400 CPI = = = 0,48 Ic 55.000 untuk f4: C 66.000 CPI = = = 1,2 Ic 55.000 0,6 + 0,36 + 0,48 + 1,2 CPI rate = = 0,66 4
x 60% x 55.000 = 33.000 x 18% x 55.000 = 19.800 x 12% x 55.000 = 26.400 12 x 10% x 55.000 = 66.000
(b) MIPS rate adalah : f 40 x10 6 MIPS rate = = = 60,61 MIPS 0,66 x10 6 CPIx10 6 (c) Pada Soal 1.4 diperoleh nilai T = 11,2 ms Sedangkan untuk multiprosesor : 10 −6 10 −6 T = Ic x = 55.000 x = 0,9075 ms 60,61 MIPS Sehingga speedup factor nya adalah : T 11,2 S(n) = = = 12,34 T (n) 0,9075 (d) Efisiensi dengan 4 prosesor adalah : S (n) 12,34 E(n) = = = 3,085 n 4
Problem 3.11 S(n) = Speedup E(n) = Efficiency U(n) = Utilization
R(n) = Redundancy Q(n) = Quality of a parallel computation
(a) Buktikan 1/n ≤ E(n) ≤ U(n) ≤ 1, dimana n = jumlah prosesor yang digunakan dalam komputasi parallel. (b) Buktikan 1 ≤ R(n) ≤ 1/E(n) ≤ n. (c) Buktikan persamaan Q(n) (Eq. 3.21) (d) Uji dengan menggunakan hypothetical workload pada contoh 3.3. Penyelesaian : (a). 1/n ≤ E(n) ≤ U(n) ≤ 1 Efisiensi diperoleh dari perbandingan antara derajat aktual dari performansi speedup S ( n) dengan nilai maksimum atau E(n) = , karena 1 ≤ S(n) ≤ n maka n 1/n ≤ S(n)/n ≤ n/n sehingga 1/n ≤ E(n) ≤ 1 (1) U(n) adalah sistem utilisasi yang didefinisikan sebagai perkalian antara redundansi R(n) dan efisiensi E(n) atau U(n) = R(n).E(n) (2) Sedangkan R(n) adalah rasio dari O(n) dan O(1), dimana rasio ini menandakan tingkat kesesuaian antara software parallelism dengan hardware parallelism oleh karena itu diketahui 1 ≤ R(n) ≤ n (3) atau nilai R(n) harus lebih besar dari satu. Dari persamaan (2) diperoleh 1/n ≤ E(n) ≤ R(n).E(n) ≤ 1 (4) Dari persamaan (1), (2), (3), dan (4) dapat diketahui bahwa pernyataan 1/n ≤ E(n) ≤ U(n) ≤ 1 adalah benar. (b). 1 ≤ R(n) ≤ 1/E(n) ≤ n Dari persamaan (2) diperoleh O ( n) nT (n) R (n) 1 nT (n) R (n) = sehingga E ( n) O ( n) pernyataan R(n) ≤ 1/E(n) dapat kita buktikan sebagai O ( n) nT (n) R( n) ≤ O(1) O ( n) 1 ≤ nT(n)R(n) (5) O(1) E(n) =
Dari persaman (3) dapat diketahui pernyataan (5) adalah benar. Diketahui juga 1/n ≤ E(n) ≤ 1 maka dari sini diperoleh n ≥ 1/E(n) ≥ 1 (6) Dari persamaan (5) dan (6) dapat diketahui bahwa pernyataan 1 ≤ R(n) ≤ 1/E(n) ≤ n adalah benar. S ( n) E ( n) T 3 (1) = (c). Q(n) = R ( n) nT 2 (n)O(n) Diketahui T (1) (7) T ( n) T (1) E(n) = (8) nT (n) O ( n) R(n) = (9) O(1) Dari persamaan (7), (8) dan (9) dapat diturunkan persamaan T (1) / T (n).T (1) / nT (n) T 3 (1) Q ( n) = = O(n) / O(1) nT 2 ( n)O(n) S(n) =
T (1).T (1) O(1) T 3 (1) . = T (n).nT (n) O(n) nT 2 (n)O(n) Diketahui bahwa dalam suatu sistem uniprosesor T(1) = O(1) maka T (1).T (1) T (1) T 3 (1) Q ( n) = . = nT (n).T (n) O(n) nT 2 (n)O(n) Q ( n) =
(d). Pada hypothetical workload pada contoh 3.3. Diketahui : O(1) = T(1) = n3 O(n) = n3 + n2 log2 n T(n) = 4n3 / (n + 3) S(n) = (n + 3) / 4 E(n) = (n + 3) / (4n) R(n) = (n + log2 n) / n U(n) = (n + 3) (n + log2 n) / (4n2) Q(n) = (n + 3)2 / (16(n + log2 n)) Misalkan jumlah prosesor yang digunakan n = 4 maka : 1/n ≤ E(n) ≤ U(n) ≤ 1 1 (n + 3) (n + 3)(n + log 2 n) ≤ ≤ ≤1 n 4n 4n 2 (4 + 3)(4 + log 2 4) (4 + 3) 1 ≤ ≤ ≤1 4(4) 4(4) 2 4
1 7 42 ≤ ≤ ≤1 4 16 64 0,25 ≤ 0,4375 ≤ 0,65625 ≤ 1 Dari perhitungan diatas maka dapat diketahui bahwa 1/n ≤ E(n) ≤ U(n) ≤ 1 adalah benar. Untuk 1 ≤ R(n) ≤ 1/E(n) ≤ n dapat dihitung pula : 1 ≤ R(n) ≤ 1/E(n) ≤ n 1 n + log 2 n 1≤ ≤ (n + 3) ≤ n n 4n 4n n + log 2 n 1≤ ≤ ≤n (n + 3) n Jika jumlah prosesor yang digunakan n = 4 maka : 4(4) 4 + log 2 4 1≤ ≤ ≤4 (4 + 3) 4 6 16 1≤ ≤ ≤n 4 7 1 ≤ 1,5 ≤ 2,2857 ≤ 4 Dari perhitungan diatas maka dapat disimpulkan bahwa 1 ≤ R(n) ≤ 1/E(n) ≤ n adalah benar. Referensi : Kai Hwang, Advanced Computer Programmability, Mc-Graw-Hill, 1993
Architecture
:
Parallelism,
Scalability,
