Materiale relativo al Homework 0
Linguaggio C su Linux
Programma di misurazione dei tempi di scansione realizzato da David Bondatti:
#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include <time.h>
#include <unistd.h>
int dim;
void scanForRows
(int *arr
) {
for (int i =
0; i < dim; i++
)
for (int j =
0; j < dim; j++
)
arr
[i*dim+j
] =
-1;
}
void scanForColumns
(int *arr
) {
for (int i =
0; i < dim; i++
)
for (int j =
0; j < dim; j++
)
arr
[j*dim+i
] =
-1;
}
int main
(int argc,
char *argv
[]) {
int *arr =
NULL;
double clockticks, cticks;
clock_t tcend, tcstart;
struct tms tmend, tmstart;
long timedif;
struct timespec tpend, tpstart;
if ((clockticks =
(double) sysconf
(_SC_CLK_TCK
)) ==
-1) {
perror
("Failed to determine clock ticks per second");
return 1;
}
printf("The number of ticks per second is %f\n", clockticks
);
if (clockticks ==
0) {
fprintf
(stderr,
"The number of ticks per second is invalid\n");
return 1;
}
for (dim =
100; dim <=
3000; dim = dim
+100) {
arr =
(int *
) realloc
(arr, dim*dim*
sizeof(int));
if (dim <
1000) {
if (clock_gettime
(CLOCK_REALTIME, &tpstart
) ==
-1) {
perror
("Failed to get starting time");
return 1;
}
scanForRows
(arr
);
if (clock_gettime
(CLOCK_REALTIME, &tpend
) ==
-1) {
perror
("Failed to get ending time");
return 1;
}
timedif = tpend.
tv_nsec - tpstart.
tv_nsec;
printf("Total time for scanForRows with dim. %d is %ld nseconds\n", dim, timedif
);
}
else {
if ((tcstart = times
(&tmstart
)) ==
-1) {
perror
("Failed to get start time");
return 1;
}
scanForRows
(arr
);
if ((tcend = times
(&tmend
)) ==
-1) {
perror
("Failed to get end times");
return 1;
}
cticks = tmend.
tms_utime + tmend.
tms_stime - tmstart.
tms_utime - tmstart.
tms_stime;
printf("Total CPU time for scanForRows with dim. %d is %f clock ticks\n", dim, cticks
);
}
}
for (dim =
100; dim <=
3000; dim = dim
+100) {
arr =
(int *
) realloc
(arr, dim*dim*
sizeof(int));
if (dim <
1000) {
if (clock_gettime
(CLOCK_REALTIME, &tpstart
) ==
-1) {
perror
("Failed to get starting time");
return 1;
}
scanForColumns
(arr
);
if (clock_gettime
(CLOCK_REALTIME, &tpend
) ==
-1) {
perror
("Failed to get ending time");
return 1;
}
timedif = tpend.
tv_nsec - tpstart.
tv_nsec;
printf("Total time for scanForColumns with dim. %d is %ld nseconds\n", dim, timedif
);
}
else {
if ((tcstart = times
(&tmstart
)) ==
-1) {
perror
("Failed to get start time");
return 1;
}
scanForColumns
(arr
);
if ((tcend = times
(&tmend
)) ==
-1) {
perror
("Failed to get end times");
return 1;
}
cticks = tmend.
tms_utime + tmend.
tms_stime - tmstart.
tms_utime - tmstart.
tms_stime;
printf("Total CPU time for scanForColumns with dim. %d is %f clock ticks\n", dim, cticks
);
}
}
free
(arr
);
return 0;
}
Esempio di esecuzione del programma:
The number of ticks per second is 100.000000
Total time for scanForRows with dim. 100 is 199112 nseconds
Total time for scanForRows with dim. 200 is 649434 nseconds
Total time for scanForRows with dim. 300 is 1336516 nseconds
Total time for scanForRows with dim. 400 is 2411065 nseconds
Total time for scanForRows with dim. 500 is 4449576 nseconds
Total time for scanForRows with dim. 600 is 5152031 nseconds
Total time for scanForRows with dim. 700 is 7067200 nseconds
Total time for scanForRows with dim. 800 is 9373936 nseconds
Total time for scanForRows with dim. 900 is 15937410 nseconds
Total CPU time for scanForRows with dim. 1000 is 2.000000 clock ticks
Total CPU time for scanForRows with dim. 1100 is 2.000000 clock ticks
Total CPU time for scanForRows with dim. 1200 is 3.000000 clock ticks
Total CPU time for scanForRows with dim. 1300 is 3.000000 clock ticks
Total CPU time for scanForRows with dim. 1400 is 3.000000 clock ticks
Total CPU time for scanForRows with dim. 1500 is 4.000000 clock ticks
Total CPU time for scanForRows with dim. 1600 is 4.000000 clock ticks
Total CPU time for scanForRows with dim. 1700 is 4.000000 clock ticks
Total CPU time for scanForRows with dim. 1800 is 5.000000 clock ticks
Total CPU time for scanForRows with dim. 1900 is 6.000000 clock ticks
Total CPU time for scanForRows with dim. 2000 is 6.000000 clock ticks
Total CPU time for scanForRows with dim. 2100 is 6.000000 clock ticks
Total CPU time for scanForRows with dim. 2200 is 8.000000 clock ticks
Total CPU time for scanForRows with dim. 2300 is 7.000000 clock ticks
Total CPU time for scanForRows with dim. 2400 is 8.000000 clock ticks
Total CPU time for scanForRows with dim. 2500 is 9.000000 clock ticks
Total CPU time for scanForRows with dim. 2600 is 9.000000 clock ticks
Total CPU time for scanForRows with dim. 2700 is 10.000000 clock ticks
Total CPU time for scanForRows with dim. 2800 is 11.000000 clock ticks
Total CPU time for scanForRows with dim. 2900 is 12.000000 clock ticks
Total CPU time for scanForRows with dim. 3000 is 12.000000 clock ticks
Total time for scanForColumns with dim. 100 is 156922 nseconds
Total time for scanForColumns with dim. 200 is 784614 nseconds
Total time for scanForColumns with dim. 300 is 2025548 nseconds
Total time for scanForColumns with dim. 400 is 3689619 nseconds
Total time for scanForColumns with dim. 500 is 5378916 nseconds
Total time for scanForColumns with dim. 600 is 8819205 nseconds
Total time for scanForColumns with dim. 700 is 11086827 nseconds
Total time for scanForColumns with dim. 800 is 22071551 nseconds
Total time for scanForColumns with dim. 900 is 19984326 nseconds
Total CPU time for scanForColumns with dim. 1000 is 3.000000 clock ticks
Total CPU time for scanForColumns with dim. 1100 is 3.000000 clock ticks
Total CPU time for scanForColumns with dim. 1200 is 4.000000 clock ticks
Total CPU time for scanForColumns with dim. 1300 is 4.000000 clock ticks
Total CPU time for scanForColumns with dim. 1400 is 5.000000 clock ticks
Total CPU time for scanForColumns with dim. 1500 is 5.000000 clock ticks
Total CPU time for scanForColumns with dim. 1600 is 7.000000 clock ticks
Total CPU time for scanForColumns with dim. 1700 is 6.000000 clock ticks
Total CPU time for scanForColumns with dim. 1800 is 8.000000 clock ticks
Total CPU time for scanForColumns with dim. 1900 is 8.000000 clock ticks
Total CPU time for scanForColumns with dim. 2000 is 9.000000 clock ticks
Total CPU time for scanForColumns with dim. 2100 is 10.000000 clock ticks
Total CPU time for scanForColumns with dim. 2200 is 11.000000 clock ticks
Total CPU time for scanForColumns with dim. 2300 is 12.000000 clock ticks
Total CPU time for scanForColumns with dim. 2400 is 14.000000 clock ticks
Total CPU time for scanForColumns with dim. 2500 is 13.000000 clock ticks
Total CPU time for scanForColumns with dim. 2600 is 16.000000 clock ticks
Total CPU time for scanForColumns with dim. 2700 is 16.000000 clock ticks
Total CPU time for scanForColumns with dim. 2800 is 20.000000 clock ticks
Total CPU time for scanForColumns with dim. 2900 is 18.000000 clock ticks
Total CPU time for scanForColumns with dim. 3000 is 20.000000 clock ticks
Misurazione dei cache miss simulati mediante il programma
Valgrind∞ della scansione per righe (5,931,342 misses) e poi di quella per colonne (94,525,306 misses):
riemann@open-amilo:~/Desktop> valgrind --tool=cachegrind ./hw0
==6013== Cachegrind, a cache and branch-prediction profiler.
==6013== Copyright (C) 2002-2007, and GNU GPL'd, by Nicholas Nethercote et al.
==6013== Using LibVEX rev 1804, a library for dynamic binary translation.
==6013== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==6013== Using valgrind-3.3.0, a dynamic binary instrumentation framework.
==6013== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==6013== For more details, rerun with: -v
==6013==
--6013-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--6013-- Simulating a 16 KB I-cache with 32 B lines
==6013==
==6013== I refs: 948,558,931
==6013== I1 misses: 2,162
==6013== L2i misses: 1,234
==6013== I1 miss rate: 0.00%
==6013== L2i miss rate: 0.00%
==6013==
==6013== D refs: 757,748,565 (662,859,532 rd + 94,889,033 wr)
==6013== D1 misses: 5,931,342 ( 18,757 rd + 5,912,585 wr)
==6013== L2d misses: 5,915,020 ( 5,754 rd + 5,909,266 wr)
==6013== D1 miss rate: 0.7% ( 0.0% + 6.2% )
==6013== L2d miss rate: 0.7% ( 0.0% + 6.2% )
==6013==
==6013== L2 refs: 5,933,504 ( 20,919 rd + 5,912,585 wr)
==6013== L2 misses: 5,916,254 ( 6,988 rd + 5,909,266 wr)
==6013== L2 miss rate: 0.3% ( 0.0% + 6.2% )
riemann@open-amilo:~/Desktop> valgrind --tool=cachegrind ./hw0
==6111== Cachegrind, a cache and branch-prediction profiler.
==6111== Copyright (C) 2002-2007, and GNU GPL'd, by Nicholas Nethercote et al.
==6111== Using LibVEX rev 1804, a library for dynamic binary translation.
==6111== Copyright (C) 2004-2007, and GNU GPL'd, by OpenWorks LLP.
==6111== Using valgrind-3.3.0, a dynamic binary instrumentation framework.
==6111== Copyright (C) 2000-2007, and GNU GPL'd, by Julian Seward et al.
==6111== For more details, rerun with: -v
==6111==
--6111-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--6111-- Simulating a 16 KB I-cache with 32 B lines
==6111==
==6111== I refs: 948,558,931
==6111== I1 misses: 2,161
==6111== L2i misses: 1,234
==6111== I1 miss rate: 0.00%
==6111== L2i miss rate: 0.00%
==6111==
==6111== D refs: 757,748,565 (662,859,532 rd + 94,889,033 wr)
==6111== D1 misses: 94,525,306 ( 18,755 rd + 94,506,551 wr)
==6111== L2d misses: 5,959,997 ( 5,754 rd + 5,954,243 wr)
==6111== D1 miss rate: 12.4% ( 0.0% + 99.5% )
==6111== L2d miss rate: 0.7% ( 0.0% + 6.2% )
==6111==
==6111== L2 refs: 94,527,467 ( 20,916 rd + 94,506,551 wr)
==6111== L2 misses: 5,961,231 ( 6,988 rd + 5,954,243 wr)
==6111== L2 miss rate: 0.3% ( 0.0% + 6.2% )
Linguaggio Java
Programma Java realizzato da Ikki Phoenix che misura i tempi di 50 scansioni indipendenti per righe (o per colonne) di una stessa matrice 12000x12000:
import java.io.*;
public class InizializzaMatrice
{
public static void main
( String [] args
)
{
final int n =
12000;
int matrix
[][] =
new int[n
][n
];
for( int t=
0; t<
50; t++
)
{
long t1 =
System.
nanoTime();
for( int i =
0; i<n; i++
)
for( int j =
0; j<n; j++
)
matrix
[i
][j
] =
1;
// oppure matrix[j][i] = 1;
long t2 =
System.
nanoTime();
System.
out.
println( (t2-t1
)/
1000000 );
}
return;
}
}