-
Notifications
You must be signed in to change notification settings - Fork 1
/
README
127 lines (90 loc) · 3.9 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
Experiment for HIGH PERFORMANCE COMPUTING
Washall's algorithms
=========================== Results ===========================
It uses staged-load blocked method for calcuation. For more information please refer to
the report.
It achieves astounding speed of 28.5 seconds for calculating the shortest path of adjacent
matrix with 17408 vertices.
The largest data I've ever tested with the CPU is 5120 vertices that cost 115 seconds
which finished in less than 1 second using CUDA(143.7x speedup).
It is anticipated that for even larger dataset the speedup might be even more significant
but I couldn't test them on my small desktop that only equipped with a 770 GTX.
=========================== Structure ===========================
input - holds the generated input file
sequential - holds the CPU implementation
washall-cpu - executable of the CPU implementation
washall-cpu [output.txt] [input.txt]
native - holds the native(CUDA) implementation
washall-cuda - executable of the CUDA implementation
washall-cuda [output.txt] [input.txt]
scripts - scripts used in makefiles & test
testgen - testfile generator
washall-test - executable of the test file generator
washall-test [N] (testfile)
=========================== Makefile ===========================
makefile contains several target:
all : make everything
clean : clean all the executables as well as *.o s generated
run : run the two implementations, regenerate testfile
exe : run the two implementations, does not regenerate testfile
diff : compare the results of two implementations
testfile : generate a test file with 2048 nodes, that is a matrix with size 2048x2048
washall-test: test generator
washall-cuda: native implementation
washall-cpu : sequential implementation on the cpu
washall-cuda uses the blocked implementation with float
===========================Compile & Execute===========================
1. First goto the root directory (project) and run:
make
or
make all
to make everything
2. Run:
make run
Executes washall-cuda as well as washall-cpu.
input will be generated with 2048 nodes and the file is located in the input directory named matrix.txt.
output will be put to the output directory with cudamatrix.txt for washall-cuda and cpumatrix.txt for washall-cpu
WARNING: test file will be remake whenever you type this.
2. To compare the result, type and enter:
make diff
if you have already run the first step this should provide you with a result stating wether the two output files differ.
=========================== Compile Only ===========================
To compile everything just run:
make all
or
make
To compile specific program:
make washall-test
for test file generator
make washall-cuda
or
make washall-cpu
To make a testfile
make testfile
will produce one with the size specified in the makefile (default 2048)
scripts/generate-testfile.sh [[Number of nodes]]
will produce one with arbitrary size
To run the test without overwriten customized testfile
make exe
========================= Changing Input size =========================
Follow the steps above or change the makefile
vim makefile
find the first line:
TESTSIZE=2048
use i or R to change it to any number you want(preferably smaller than 17408, largest I've ever tested, that is over 2GB in memory!)
============================ Other scripts ============================
scripts/time.sh [[program]]
This script times the program with input size from 1024 to 17408 at step length 1024
the script will stop when ever the average execution time(5 times) execeed one minute
the results is writen to [[program]].log
for example, run:
scripts/time.sh native/washall-cuda
The scripts will start running automatically, and prints its result to the log file:
native/washall-cuda.log:
1024 10.5695
2048 65.5086
...
...
...
16384 23661.6
17408 28533.8