DisCostiC v2.0.0
Distributed Cost in Cluster: a cross-architecture simulator for massively parallel MPI programs
Loading...
Searching...
No Matches
CollectiveModel.hpp
Go to the documentation of this file.
1
3
4#ifndef COLLECTIVEMODEL_HPP
5#define COLLECTIVEMODEL_HPP
6
7#pragma once
8
9#include <cmath>
10#include <algorithm>
11#include "DataType.hpp"
12#include "enum.hpp"
13
14namespace DisCosTiC {
15
17 public:
18 //bcast time using binomial tree
22 DisCosTiC_Datatype numRanks,
23 DisCosTiC_Datatype messageSize,
28 DisCosTiC_Timetype inverse_bandwidth = 0,
29 DisCosTiC_Datatype eagerLimit = 65535)
30 {
31 if (numRanks <= 1) return 0;
32
33 DisCosTiC_Timetype stageTime = L + o;
34 if (messageSize > 0) {
35 if (messageSize <= eagerLimit) {
36 //eager protocol bottleneck is max of sender/receiver gaps
37 stageTime += messageSize * std::max(g, G);
38 } else {
39 //rdvz protocol bandwidth limited
40 stageTime += messageSize * inverse_bandwidth;
41 }
42 }
43
44 //calculate relative rank from root
45 DisCosTiC_Datatype relRank = (rank + numRanks - root) % numRanks;
46
47 //root is special case
48 if (relRank == 0) {
49 //root sends at multiple stages
50 DisCosTiC_Datatype totalStages = static_cast<DisCosTiC_Datatype>(
51 std::ceil(std::log2(numRanks))
52 );
53 //root completes after last send
54 return totalStages * stageTime;
55 }
56
57 //for non root find when receive
58 //rank receives at log stage
59 DisCosTiC_Datatype receiveStage = static_cast<DisCosTiC_Datatype>(
60 std::ceil(std::log2(relRank + 1)) - 1
61 );
62
63 //time when rank receives
64 DisCosTiC_Timetype receiveTime = receiveStage * stageTime;
65
66 //find last stage where rank sends
67 DisCosTiC_Datatype lastSendStage = receiveStage;
68 DisCosTiC_Datatype totalStages = static_cast<DisCosTiC_Datatype>(
69 std::ceil(std::log2(numRanks))
70 );
71
72 //check each subsequent stage to see if send
73 for (DisCosTiC_Datatype stage = receiveStage + 1; stage < totalStages; stage++) {
74 DisCosTiC_Datatype distance = 1 << stage;
75 if (relRank + distance < numRanks) {
76 //send at this stage
77 lastSendStage = stage;
78 }
79 }
80
81 //never send after receiving = leaf
82 if (lastSendStage == receiveStage) {
83 //leafs completes immediately after receiving
84 return receiveTime;
85 }
86
87 //complete after last send
88 return (lastSendStage + 1) * stageTime;
89 }
90
91 //bcast time using ring algo
95 DisCosTiC_Datatype numRanks,
96 DisCosTiC_Datatype messageSize,
101 DisCosTiC_Timetype inverse_bandwidth = 0,
102 DisCosTiC_Datatype eagerLimit = 65535)
103 {
104 DisCosTiC_Timetype hopTime = L + o;
105 if (messageSize > 0) {
106 if (messageSize <= eagerLimit) {
107 //eager protocol
108 hopTime += messageSize * std::max(g, G);
109 } else {
110 //rdvz protocol bandwidth limited
111 hopTime += messageSize * inverse_bandwidth;
112 }
113 }
114
115 //message is sent sequentially through all ranks
116 //(numRanks-1) hops
117 DisCosTiC_Timetype totalTime = (numRanks - 1) * hopTime;
118
119 DisCosTiC_Datatype distance = (rank + numRanks - root) % numRanks;
120 DisCosTiC_Timetype receiveTime = distance * hopTime;
121 return totalTime;
122 }
123
124 //reduce time using binomial tree algo (inverse of bcast)
128 DisCosTiC_Datatype numRanks,
129 DisCosTiC_Datatype messageSize,
134 DisCosTiC_Timetype gamma = 0,
135 DisCosTiC_Timetype inverse_bandwidth = 0,
136 DisCosTiC_Datatype eagerLimit = 65535)
137 {
138 if (numRanks <= 1) return 0;
139
140 DisCosTiC_Datatype numStages =
141 static_cast<DisCosTiC_Datatype>(std::ceil(std::log2(numRanks)));
142
143 DisCosTiC_Timetype stageTime = L + o + gamma;
144 if (messageSize > 0) {
145 if (messageSize <= eagerLimit) {
146 //eager protocol bottleneck is max of sender/receiver gaps
147 stageTime += messageSize * std::max(g, G);
148 } else {
149 //rdvz protocol bandwidth limited
150 stageTime += messageSize * inverse_bandwidth;
151 }
152 }
153
154 if (rank == root) {
155 return numStages * stageTime; //root waits all stages
156 }
157
158 DisCosTiC_Datatype distance = (rank + numRanks - root) % numRanks;
159 DisCosTiC_Datatype rankStage =
160 static_cast<DisCosTiC_Datatype>(std::ceil(std::log2(distance + 1)));
161
162 return (rankStage + 1) * stageTime; //shift by 1 for non root
163 }
164
165 //allreduce time same for all ranks
168 DisCosTiC_Datatype numRanks,
169 DisCosTiC_Datatype messageSize,
174 DisCosTiC_Timetype gamma = 0,
175 DisCosTiC_Timetype inverse_bandwidth = 0,
176 DisCosTiC_Datatype eagerLimit = 65535)
177 {
178 if (numRanks <= 1) return 0;
179
180 DisCosTiC_Datatype numStages =
181 static_cast<DisCosTiC_Datatype>(std::ceil(std::log2(numRanks)));
182 DisCosTiC_Datatype totalStages = 2 * numStages;
183
184 DisCosTiC_Timetype stageTime = L + o;
185 if (messageSize > 0) {
186 if (messageSize <= eagerLimit) {
187 //eager protocol bottleneck is max of sender/receiver gaps
188 stageTime += messageSize * std::max(g, G);
189 } else {
190 //rdvz protocol bandwidth limited
191 stageTime += messageSize * inverse_bandwidth;
192 }
193 }
194
195 DisCosTiC_Datatype rankOffset = rank % numStages;
196 DisCosTiC_Timetype rankDelay = rankOffset * (stageTime * 0.1); //small variation/delay depending on rank
197
198 return totalStages * stageTime + numStages * gamma + rankDelay;
199 }
200
201 //calculating collective time with algo selection
203 CollectiveType collectiveType,
206 DisCosTiC_Datatype numRanks,
207 DisCosTiC_Datatype messageSize,
212 uint8_t algorithm = 0,
213 DisCosTiC_Timetype inverse_bandwidth = 0,
214 DisCosTiC_Datatype eagerLimit = 65535)
215 {
216 switch(collectiveType) {
217 case COLL_BCAST: {
218 BcastAlgorithm algo = static_cast<BcastAlgorithm>(algorithm);
219 if (algo == BCAST_RING) {
220 return calculateRingBroadcast(rank, root, numRanks, messageSize, L, o, g, G, inverse_bandwidth, eagerLimit);
221 } else {
222 //all tree variants use binomial tree
223 return calculateBinomialTreeBroadcast(rank, root, numRanks, messageSize, L, o, g, G, inverse_bandwidth, eagerLimit);
224 }
225 }
226 case COLL_REDUCE: {
227 DisCosTiC_Timetype gamma = messageSize * 0.001; //computation overhead per byte for reduction ops
228 return calculateBinomialTreeReduce(rank, root, numRanks, messageSize, L, o, g, G, gamma, inverse_bandwidth, eagerLimit);
229 }
230 case COLL_ALLREDUCE: {
231 DisCosTiC_Timetype gamma = 0; //computation overhead
232 return calculateAllreduce(rank, numRanks, messageSize, L, o, g, G, gamma, inverse_bandwidth, eagerLimit);
233 }
234
235
236 default:
237 return calculateBinomialTreeBroadcast(rank, root, numRanks, messageSize, L, o, g, G);
238 }
239 }
240 };
241
242}
243
244#endif
std::size_t DisCosTiC_Datatype
Definition DataType.hpp:52
double DisCosTiC_Timetype
Definition DataType.hpp:51
static DisCosTiC_Timetype calculateBinomialTreeBroadcast(DisCosTiC_Datatype rank, DisCosTiC_Datatype root, DisCosTiC_Datatype numRanks, DisCosTiC_Datatype messageSize, DisCosTiC_Timetype L, DisCosTiC_Timetype o, DisCosTiC_Timetype g, DisCosTiC_Timetype G, DisCosTiC_Timetype inverse_bandwidth=0, DisCosTiC_Datatype eagerLimit=65535)
static DisCosTiC_Timetype calculateRingBroadcast(DisCosTiC_Datatype rank, DisCosTiC_Datatype root, DisCosTiC_Datatype numRanks, DisCosTiC_Datatype messageSize, DisCosTiC_Timetype L, DisCosTiC_Timetype o, DisCosTiC_Timetype g, DisCosTiC_Timetype G, DisCosTiC_Timetype inverse_bandwidth=0, DisCosTiC_Datatype eagerLimit=65535)
static DisCosTiC_Timetype calculateAllreduce(DisCosTiC_Datatype rank, DisCosTiC_Datatype numRanks, DisCosTiC_Datatype messageSize, DisCosTiC_Timetype L, DisCosTiC_Timetype o, DisCosTiC_Timetype g, DisCosTiC_Timetype G, DisCosTiC_Timetype gamma=0, DisCosTiC_Timetype inverse_bandwidth=0, DisCosTiC_Datatype eagerLimit=65535)
static DisCosTiC_Timetype calculateBinomialTreeReduce(DisCosTiC_Datatype rank, DisCosTiC_Datatype root, DisCosTiC_Datatype numRanks, DisCosTiC_Datatype messageSize, DisCosTiC_Timetype L, DisCosTiC_Timetype o, DisCosTiC_Timetype g, DisCosTiC_Timetype G, DisCosTiC_Timetype gamma=0, DisCosTiC_Timetype inverse_bandwidth=0, DisCosTiC_Datatype eagerLimit=65535)
static DisCosTiC_Timetype calculateCollectiveTime(CollectiveType collectiveType, DisCosTiC_Datatype rank, DisCosTiC_Datatype root, DisCosTiC_Datatype numRanks, DisCosTiC_Datatype messageSize, DisCosTiC_Timetype L, DisCosTiC_Timetype o, DisCosTiC_Timetype g, DisCosTiC_Timetype G, uint8_t algorithm=0, DisCosTiC_Timetype inverse_bandwidth=0, DisCosTiC_Datatype eagerLimit=65535)
< benchmark test cases
BcastAlgorithm
Definition enum.hpp:44
@ BCAST_RING
Definition enum.hpp:46
CollectiveType
Definition enum.hpp:38
@ COLL_BCAST
Definition enum.hpp:39
@ COLL_ALLREDUCE
Definition enum.hpp:41
@ COLL_REDUCE
Definition enum.hpp:40