program ProgTest = { 3, 0, 91, -1, -1, -1, 4, 2, 59, 0, -1, -1, 6, 14,100, 0, 0, 0, 6, 7, 11, 14, 14, 14, 4, 2, 4, 0, -1, -1, 4, 4, 40, 0, -1, -1, 4, 13, 17, 0, -1, -1, 5, 4, 52, 13, 0, -1, 4, 5, 22, 2, -1, -1, 4, 17, 21, 13, -1, -1, 4, 4, 1, 5, -1, -1, 4, 13, 17, 0, -1, -1, 4, 8, 8, 17, -1, -1, 5, 14, 3, 13, 8, -1, 6, 19, 66, 2, 17, 0, 6, 16, 28, 13, 13, 13, 4, 3, 16, 2, -1, -1, 4, 5, 81, 17, -1, -1, 6, 11, 69, 19, 13, 19, 5, 9, 81, 3, 19, -1, } ; /* TRACE D'EXECUTION FOURNIE PAR LES ENSEIGNANTS: Program: 0: x0 := 91 ; 1: x2 := 59 + x0 ; 2: x14 := 100 + x0 + x0 + x0 ; 3: x7 := 11 + x14 + x14 + x14 ; 4: x2 := 4 + x0 ; 5: x4 := 40 + x0 ; 6: x13 := 17 + x0 ; 7: x4 := 52 + x13 + x0 ; 8: x5 := 22 + x2 ; 9: x17 := 21 + x13 ; 10: x4 := 1 + x5 ; 11: x13 := 17 + x0 ; 12: x8 := 8 + x17 ; 13: x14 := 3 + x13 + x8 ; 14: x19 := 66 + x2 + x17 + x0 ; 15: x16 := 28 + x13 + x13 + x13 ; 16: x3 := 16 + x2 ; 17: x5 := 81 + x17 ; 18: x11 := 69 + x19 + x13 + x19 ; 19: x9 := 81 + x3 + x19 ; Memory: x0=? x2=? x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? x14=? x16=? x17=? x19=? Execute instruction 0: x0 := 91 = 91 = 91 Memory: [[ x0=91 ]] x2=? x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? x14=? x16=? x17=? x19=? Execute instruction 1: x2 := 59 + x0 = 59+91 = 150 Memory: x0=91 [[ x2=150 ]] x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? x14=? x16=? x17=? x19=? Execute instruction 2: x14 := 100 + x0 + x0 + x0 = 100+91+91+91 = 373 Memory: x0=91 x2=150 x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? [[ x14=373 ]] x16=? x17=? x19=? Execute instruction 3: x7 := 11 + x14 + x14 + x14 = 11+373+373+373 = 1130 Memory: x0=91 x2=150 x3=? x4=? x5=? [[ x7=1130 ]] x8=? x9=? x11=? x13=? x14=373 x16=? x17=? x19=? Execute instruction 4: x2 := 4 + x0 = 4+91 = 95 Memory: x0=91 [[ x2=95 ]] x3=? x4=? x5=? x7=1130 x8=? x9=? x11=? x13=? x14=373 x16=? x17=? x19=? Execute instruction 5: x4 := 40 + x0 = 40+91 = 131 Memory: x0=91 x2=95 x3=? [[ x4=131 ]] x5=? x7=1130 x8=? x9=? x11=? x13=? x14=373 x16=? x17=? x19=? Execute instruction 6: x13 := 17 + x0 = 17+91 = 108 Memory: x0=91 x2=95 x3=? x4=131 x5=? x7=1130 x8=? x9=? x11=? [[ x13=108 ]] x14=373 x16=? x17=? x19=? Execute instruction 7: x4 := 52 + x13 + x0 = 52+108+91 = 251 Memory: x0=91 x2=95 x3=? [[ x4=251 ]] x5=? x7=1130 x8=? x9=? x11=? x13=108 x14=373 x16=? x17=? x19=? Execute instruction 8: x5 := 22 + x2 = 22+95 = 117 Memory: x0=91 x2=95 x3=? x4=251 [[ x5=117 ]] x7=1130 x8=? x9=? x11=? x13=108 x14=373 x16=? x17=? x19=? Execute instruction 9: x17 := 21 + x13 = 21+108 = 129 Memory: x0=91 x2=95 x3=? x4=251 x5=117 x7=1130 x8=? x9=? x11=? x13=108 x14=373 x16=? [[ x17=129 ]] x19=? Execute instruction 10: x4 := 1 + x5 = 1+117 = 118 Memory: x0=91 x2=95 x3=? [[ x4=118 ]] x5=117 x7=1130 x8=? x9=? x11=? x13=108 x14=373 x16=? x17=129 x19=? Execute instruction 11: x13 := 17 + x0 = 17+91 = 108 Memory: x0=91 x2=95 x3=? x4=118 x5=117 x7=1130 x8=? x9=? x11=? x13=108 x14=373 x16=? x17=129 x19=? Execute instruction 12: x8 := 8 + x17 = 8+129 = 137 Memory: x0=91 x2=95 x3=? x4=118 x5=117 x7=1130 [[ x8=137 ]] x9=? x11=? x13=108 x14=373 x16=? x17=129 x19=? Execute instruction 13: x14 := 3 + x13 + x8 = 3+108+137 = 248 Memory: x0=91 x2=95 x3=? x4=118 x5=117 x7=1130 x8=137 x9=? x11=? x13=108 [[ x14=248 ]] x16=? x17=129 x19=? Execute instruction 14: x19 := 66 + x2 + x17 + x0 = 66+95+129+91 = 381 Memory: x0=91 x2=95 x3=? x4=118 x5=117 x7=1130 x8=137 x9=? x11=? x13=108 x14=248 x16=? x17=129 [[ x19=381 ]] Execute instruction 15: x16 := 28 + x13 + x13 + x13 = 28+108+108+108 = 352 Memory: x0=91 x2=95 x3=? x4=118 x5=117 x7=1130 x8=137 x9=? x11=? x13=108 x14=248 [[ x16=352 ]] x17=129 x19=381 Execute instruction 16: x3 := 16 + x2 = 16+95 = 111 Memory: x0=91 x2=95 [[ x3=111 ]] x4=118 x5=117 x7=1130 x8=137 x9=? x11=? x13=108 x14=248 x16=352 x17=129 x19=381 Execute instruction 17: x5 := 81 + x17 = 81+129 = 210 Memory: x0=91 x2=95 x3=111 x4=118 [[ x5=210 ]] x7=1130 x8=137 x9=? x11=? x13=108 x14=248 x16=352 x17=129 x19=381 Execute instruction 18: x11 := 69 + x19 + x13 + x19 = 69+381+108+381 = 939 Memory: x0=91 x2=95 x3=111 x4=118 x5=210 x7=1130 x8=137 x9=? [[ x11=939 ]] x13=108 x14=248 x16=352 x17=129 x19=381 Execute instruction 19: x9 := 81 + x3 + x19 = 81+111+381 = 573 Memory: x0=91 x2=95 x3=111 x4=118 x5=210 x7=1130 x8=137 [[ x9=573 ]] x11=939 x13=108 x14=248 x16=352 x17=129 x19=381 Program: 0: x0 := 91 ; 1: x2 := 59 + x0 ; 2: x14 := 100 + x0 + x0 + x0 ; 3: x7 := 11 + x14 + x14 + x14 ; 4: x2 := 4 + x0 ; 5: x4 := 40 + x0 ; 6: x13 := 17 + x0 ; 7: x4 := 52 + x13 + x0 ; 8: x5 := 22 + x2 ; 9: x17 := 21 + x13 ; 10: x4 := 1 + x5 ; 11: x13 := 17 + x0 ; 12: x8 := 8 + x17 ; 13: x14 := 3 + x13 + x8 ; 14: x19 := 66 + x2 + x17 + x0 ; 15: x16 := 28 + x13 + x13 + x13 ; 16: x3 := 16 + x2 ; 17: x5 := 81 + x17 ; 18: x11 := 69 + x19 + x13 + x19 ; 19: x9 := 81 + x3 + x19 ; Before = 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|19| 0: | <| <| | <| <| <| <| | | | <| | | <| | | | | | 1: | | | | <| | | | | | | | | | | | | | | | 2: | | | <| | | | | | | | | | <| | | | | | | 3: | | | | | | | | | | | | | <| | | | | | | 4: | | | | | | | | <| | | | | | <| | <| | | | 5: | | | | | | | <| | | | | | | | | | | | | 6: | | | | | | | <| | <| | <| | | | | | | | | 7: | | | | | | | | | | <| <| | | | | | | | | 8: | | | | | | | | | | <| | | | | | | <| | | 9: | | | | | | | | | | | <| <| | <| | | <| | | 10: | | | | | | | | | | | | | | | | | <| | | 11: | | | | | | | | | | | | | <| | <| | | <| | 12: | | | | | | | | | | | | | <| | | | | | | 13: | | | | | | | | | | | | | | | | | | | | 14: | | | | | | | | | | | | | | | | | | <| <| 15: | | | | | | | | | | | | | | | | | | | | 16: | | | | | | | | | | | | | | | | | | | <| 17: | | | | | | | | | | | | | | | | | | | | 18: | | | | | | | | | | | | | | | | | | | | 19: | | | | | | | | | | | | | | | | | | | | Calcul des termes de la suite jusqu'à atteindre la cloture transitive: 1.2.3.4. stabilité! cloture_transitive_Before = 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|19| 0: | <| <| <| <| <| <| <| <| <| <| <| <| <| <| <| <| <| <| <| 1: | | | | <| | | | <| | <| | | | <| | <| <| <| <| 2: | | | <| | | | | | | | | | <| | | | | | | 3: | | | | | | | | | | | | | <| | | | | | | 4: | | | | | | | | <| | <| | | | <| | <| <| <| <| 5: | | | | | | | <| | | <| <| | <| | <| | <| <| | 6: | | | | | | | <| | <| <| <| <| <| <| <| | <| <| <| 7: | | | | | | | | | | <| <| | <| | <| | <| <| | 8: | | | | | | | | | | <| | | | | | | <| | | 9: | | | | | | | | | | | <| <| <| <| <| | <| <| <| 10: | | | | | | | | | | | | | | | | | <| | | 11: | | | | | | | | | | | | | <| | <| | | <| | 12: | | | | | | | | | | | | | <| | | | | | | 13: | | | | | | | | | | | | | | | | | | | | 14: | | | | | | | | | | | | | | | | | | <| <| 15: | | | | | | | | | | | | | | | | | | | | 16: | | | | | | | | | | | | | | | | | | | <| 17: | | | | | | | | | | | | | | | | | | | | 18: | | | | | | | | | | | | | | | | | | | | 19: | | | | | | | | | | | | | | | | | | | | Placement (height,width) = (4,5): line 0 = | 0 | __ | __ | __ | __ | __ | __ | __ | __ | __ | line 1 = | 1 | 2 | 5 | 6 | __ | __ | __ | __ | __ | __ | line 2 = | 3 | 4 | 7 | 9 | __ | __ | __ | __ | __ | __ | line 3 = | 8 | 12 | 11 | 14 | 15 | 16 | __ | __ | __ | __ | line 4 = | 10 | 13 | 18 | 19 | __ | __ | __ | __ | __ | __ | line 5 = | 17 | __ | __ | __ | __ | __ | __ | __ | __ | __ | Program: 0: x0 := 91 ; 1: x2 := 59 + x0 ; 2: x14 := 100 + x0 + x0 + x0 ; 3: x7 := 11 + x14 + x14 + x14 ; 4: x2 := 4 + x0 ; 5: x4 := 40 + x0 ; 6: x13 := 17 + x0 ; 7: x4 := 52 + x13 + x0 ; 8: x5 := 22 + x2 ; 9: x17 := 21 + x13 ; 10: x4 := 1 + x5 ; 11: x13 := 17 + x0 ; 12: x8 := 8 + x17 ; 13: x14 := 3 + x13 + x8 ; 14: x19 := 66 + x2 + x17 + x0 ; 15: x16 := 28 + x13 + x13 + x13 ; 16: x3 := 16 + x2 ; 17: x5 := 81 + x17 ; 18: x11 := 69 + x19 + x13 + x19 ; 19: x9 := 81 + x3 + x19 ; Memory: x0=? x2=? x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? x14=? x16=? x17=? x19=? Execute placement line 0 = | 0 | __ | __ | __ | __ | __ | __ | __ | __ | __ | . instruction 0: x0 := 91 = 91 = 91 Memory: [[ x0=91 ]] x2=? x3=? x4=? x5=? x7=? x8=? x9=? x11=? x13=? x14=? x16=? x17=? x19=? Execute placement line 1 = | 1 | 2 | 5 | 6 | __ | __ | __ | __ | __ | __ | . instruction 1: x2 := 59 + x0 = 59+91 = 150 . instruction 2: x14 := 100 + x0 + x0 + x0 = 100+91+91+91 = 373 . instruction 5: x4 := 40 + x0 = 40+91 = 131 . instruction 6: x13 := 17 + x0 = 17+91 = 108 Memory: x0=91 [[ x2=150 ]] x3=? [[ x4=131 ]] x5=? x7=? x8=? x9=? x11=? [[ x13=108 ]] [[ x14=373 ]] x16=? x17=? x19=? Execute placement line 2 = | 3 | 4 | 7 | 9 | 11 | __ | __ | __ | __ | __ | . instruction 3: x7 := 11 + x14 + x14 + x14 = 11+373+373+373 = 1130 . instruction 4: x2 := 4 + x0 = 4+91 = 95 . instruction 7: x4 := 52 + x13 + x0 = 52+108+91 = 251 . instruction 9: x17 := 21 + x13 = 21+108 = 129 Memory: x0=91 [[ x2=95 ]] x3=? [[ x4=251 ]] x5=? [[ x7=1130 ]] x8=? x9=? x11=? x13=108 x14=373 x16=? [[ x17=129 ]] x19=? Execute placement line 3 = | 8 | 12 | 14 | 15 | 16 | __ | __ | __ | __ | __ | . instruction 8: x5 := 22 + x2 = 22+95 = 117 . instruction 12: x8 := 8 + x17 = 8+129 = 137 . instruction 11: x13 := 17 + x0 = 17+91 = 108 . instruction 14: x19 := 66 + x2 + x17 + x0 = 66+95+129+91 = 381 . instruction 15: x16 := 28 + x13 + x13 + x13 = 28+108+108+108 = 352 . instruction 16: x3 := 16 + x2 = 16+95 = 111 Memory: x0=91 x2=95 [[ x3=111 ]] x4=251 [[ x5=117 ]] x7=1130 [[ x8=137 ]] x9=? x11=? [[ x13=108 ]] x14=373 [[ x16=352 ]] x17=129 [[ x19=381 ]] Execute placement line 4 = | 10 | 13 | 18 | 19 | 17 | __ | __ | __ | __ | __ | . instruction 10: x4 := 1 + x5 = 1+117 = 118 . instruction 13: x14 := 3 + x13 + x8 = 3+108+137 = 248 . instruction 18: x11 := 69 + x19 + x13 + x19 = 69+381+108+381 = 939 . instruction 19: x9 := 81 + x3 + x19 = 81+111+381 = 573 Memory: x0=91 x2=95 x3=111 [[ x4=118 ]] x5=117 x7=1130 x8=137 [[ x9=573 ]] [[ x11=939 ]] x13=108 [[ x14=248 ]] x16=352 x17=129 x19=381 Execute placement line 5 = | 17 | __ | __ | __ | __ | __ | __ | __ | __ | __ | . instruction 17: x5 := 81 + x17 = 81+129 = 210 Memory: x0=91 x2=95 x3=111 x4=118 [[ x5=210 ]] x7=1130 x8=137 x9=573 x11=939 x13=108 x14=248 x16=352 x17=129 x19=381 COMPARAISON DES MÉMOIRES OBTENUES PAR LES 2 EXÉCUTIONS 1. Mémoire obtenue par l'exécution non optimisée du programme: Memory: x0=91 x2=95 x3=111 x4=118 x5=210 x7=1130 x8=137 x9=573 x11=939 x13=108 x14=248 x16=352 x17=129 x19=381 2. Mémoire obtenue par l'exécution du placement du programme sur un processeur à 10 coeurs: Memory: x0=91 x2=95 x3=111 x4=118 x5=210 x7=1130 x8=137 x9=573 x11=939 x13=108 x14=248 x16=352 x17=129 x19=381 3. Différences entre les mémoires: les valeurs différentes sont indiquées entre [[ ]] Memory: x0=91 x2=95 x3=111 x4=118 x5=210 x7=1130 x8=137 x9=573 x11=939 x13=108 x14=248 x16=352 x17=129 x19=381 ******************* PLACEMENT CORRECT ******************* */