-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdijk_inner_mp.py
executable file
·144 lines (120 loc) · 3.18 KB
/
dijk_inner_mp.py
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import random
import time
import sys
import multiprocessing
from multiprocessing import Lock,Process,Semaphore,Barrier,Array,Queue
INT_MAX = multiprocessing.Value('i',1000000000)
#N=multiprocessing.Value('i',16384)
#DEG=multiprocessing.Value('i',16)
#P=multiprocessing.Value('i',2)
q = multiprocessing.Queue()
N1=int(sys.argv[2])
DEG1=int(sys.argv[3])
P1=int(sys.argv[1])
W = [[0 for x in range(DEG1)] for x in range(N1)]
W_index = [[0 for x in range(DEG1)] for x in range(N1)]
u = multiprocessing.Array('i',range(P1))
D = multiprocessing.Array('i',range(N1))
Q = multiprocessing.Array('i',range(N1))
l = [multiprocessing.Lock() for i in range(0,N1)]
INT_MAX1=1000000000
barrier = Barrier(P1)
local_min = multiprocessing.Array('i',range(P1))
def graph():
global W
global W_index
global P
global INT_MAX
global D
global Q
global u
global local_min
global l
for i in range(0,N1):
for j in range(0,DEG1):
W_index[i][j] = i+j
W[i][j] = i+j#random.randint(1,3)+i
if W_index[i][j] >= N1-1 :
W_index[i][j] = N1-1
#W[i][j] = N-1 random.randint(1, 10) + i
if i==i+j:
W[i][j]=0
#print (W[i][j], W_index[i][j])
#print (' ')
def array_init():
for i in range(0,N1):
D[i] = INT_MAX1
Q[i] = 1
D[0] = 0
def do_work(tid,D,Q,N,DEG,P,u):
start_time = time.time()
local_count=N.value
N=N.value
DEG=DEG.value
P=P.value
INT_MAX2=INT_MAX.value
u[tid]=0
i_start = tid*DEG/P
i_stop = (tid+1)*DEG/P
barrier.wait()
while local_count!=0: #outer loop
min1 = INT_MAX2
min_index1 = N-1
for j in range(int(i_start),int(i_stop)): #local_min
if(D[W_index[u[tid]][j]] < min1 and Q[W_index[u[tid]][j]]==1): #inner loop
min1 = D[W_index[u[tid]][j]]
min_index1 = W_index[u[tid]][j]
local_min[tid]=min_index1
barrier.wait() #barrier
if tid==0 :
min2=INT_MAX2
min_index2=N-1
for k in range(0,P):
if D[local_min[k]] < min2 and Q[local_min[k]]==1:
min2 = D[local_min[k]]
min_index2 = local_min[k]
u[tid]=min_index2;
Q[u[tid]]=0
barrier.wait()
if tid!=0:
u[tid]=u[0]
for i in range(int(i_start),int(i_stop)):
if(D[W_index[u[tid]][i]] > D[u[tid]] + W[u[tid]][i]):
D[W_index[u[tid]][i]] = D[u[tid]] + W[u[tid]][i] #relax
local_count = local_count - 1
final_time = time.time() - start_time
print ('TID:',tid,'TIME_SEC',final_time)
strr0 = "inner/inner"
strr1 = str(P)
strr11 = str(N)
strr12 = str(DEG)
strr2 = ".out"
strr3 = "-"
strr_final = strr0 + strr3 + strr1 + strr3 + strr11 + strr3 + strr12 + strr2
f = open(strr_final,'w')
f.write(str(final_time))
f.close
#if tid==0:
# for i in range(0,N):
# print (D[i],Q[i])
def main():
graph()
array_init()
P11 = int(sys.argv[1])
N11 = int(sys.argv[2])
DEG11 = int(sys.argv[3])
print (P11)
P1 = P11
N1 = N11
DEG1 = DEG11
P = multiprocessing.Value('i',P11)
N = multiprocessing.Value('i',N11)
DEG = multiprocessing.Value('i',DEG11)
for i in range(1,P1):
p = Process(target=do_work,args=(i,D,Q,N,DEG,P,u))
p.start()
do_work(0,D,Q,N,DEG,P,u)
for i in range(1,P1):
p.join()
if __name__ == "__main__":
main()