00001
00002 #include "sim/builder.hh"
00003 #include "butterfly.hh"
00004
00005 #include <math.h>
00006
00007 using namespace std;
00008
00009 Butterfly::Butterfly(const std::string &_name,
00010 int _width,
00011 int _clock,
00012 int _transDelay,
00013 int _arbDelay,
00014 int _cpu_count,
00015 HierParams *_hier,
00016 int _switchDelay,
00017 int _radix,
00018 int _banks)
00019 : Interconnect(_name,
00020 _width,
00021 _clock,
00022 _transDelay,
00023 _arbDelay,
00024 _cpu_count,
00025 _hier)
00026 {
00027 switchDelay = _switchDelay;
00028 radix = _radix;
00029 butterflyCpuCount = _cpu_count;
00030 butterflyCacheBanks = _banks;
00031
00032 if(butterflyCacheBanks != 4){
00033 fatal("mappings only implemented for 4 L2 cache banks");
00034 }
00035
00036 if(cpu_count == 2){
00037
00038 cpuIDtoNode[0] = 0;
00039 cpuIDtoNode[1] = 1;
00040
00041 l2IDtoNode[0] = 2;
00042 l2IDtoNode[1] = 2;
00043 l2IDtoNode[2] = 3;
00044 l2IDtoNode[3] = 3;
00045
00046 terminalNodes = 4;
00047 }
00048 else if(cpu_count == 4){
00049
00050 cpuIDtoNode[0] = 0;
00051 cpuIDtoNode[1] = 1;
00052 cpuIDtoNode[2] = 2;
00053 cpuIDtoNode[3] = 3;
00054
00055 l2IDtoNode[0] = 4;
00056 l2IDtoNode[1] = 5;
00057 l2IDtoNode[2] = 6;
00058 l2IDtoNode[3] = 7;
00059
00060 terminalNodes = 8;
00061 }
00062 else if(cpu_count == 8){
00063
00064 cpuIDtoNode[0] = 0;
00065 cpuIDtoNode[1] = 1;
00066 cpuIDtoNode[2] = 2;
00067 cpuIDtoNode[3] = 3;
00068 cpuIDtoNode[4] = 4;
00069 cpuIDtoNode[5] = 5;
00070 cpuIDtoNode[6] = 6;
00071 cpuIDtoNode[7] = 7;
00072
00073 cpuIDtoNode[8] = -1;
00074 cpuIDtoNode[9] = -1;
00075 cpuIDtoNode[10] = -1;
00076 cpuIDtoNode[11] = -1;
00077
00078 l2IDtoNode[0] = 12;
00079 l2IDtoNode[1] = 13;
00080 l2IDtoNode[2] = 14;
00081 l2IDtoNode[3] = 15;
00082
00083 terminalNodes = 16;
00084 }
00085 else{
00086 fatal("The butterfly only supports 2, 4 or 8 processors");
00087 }
00088
00089
00090
00091 stages = (int) (log10((double) terminalNodes) / log10((double) radix));
00092 switches = stages * (terminalNodes / radix);
00093 butterflyHeight = (terminalNodes / radix);
00094 hopCount = stages + 1;
00095 chanBetweenStages = butterflyHeight * radix;
00096 int totalChannels = hopCount * chanBetweenStages;
00097
00098 butterflyStatus.insert(butterflyStatus.begin(), totalChannels, false);
00099 channelUsage.insert(channelUsage.begin(), totalChannels, 0);
00100
00101 if(radix != 2) fatal("Only radix 2 butterflies are implemented");
00102 }
00103
00104 void
00105 Butterfly::request(Tick time, int fromID){
00106
00107 requests++;
00108
00109 if(requestQueue.empty() || requestQueue.back()->time < time){
00110 requestQueue.push_back(new InterconnectRequest(time, fromID));
00111 }
00112 else{
00113 list<InterconnectRequest*>::iterator pos;
00114 for(pos = requestQueue.begin();
00115 pos != requestQueue.end();
00116 pos++){
00117 if((*pos)->time > time) break;
00118 }
00119 requestQueue.insert(pos, new InterconnectRequest(time, fromID));
00120 }
00121
00122 assert(isSorted(&requestQueue));
00123
00124 if(!blocked) scheduleArbitrationEvent(time + arbitrationDelay);
00125 }
00126
00127 void
00128 Butterfly::send(MemReqPtr& req, Tick time, int fromID){
00129
00130 assert(!blocked);
00131 assert((req->size / width) <= 1);
00132
00133 int toID = -1;
00134 if(allInterfaces[fromID]->isMaster() && req->toInterfaceID != -1){
00135 toID = req->toInterfaceID;
00136 }
00137 else if(allInterfaces[fromID]->isMaster()){
00138 toID = getTarget(req->paddr);
00139 }
00140 else{
00141 toID = req->fromInterfaceID;
00142 }
00143
00144 deliverQueue.push_back(new InterconnectDelivery(time, fromID, toID, req));
00145
00146
00147 Tick deliverTime = time + (stages*switchDelay + hopCount*transferDelay);
00148 bool found = false;
00149 for(int i=0;i<deliverEvents.size();i++){
00150 if(deliverEvents[i]->when() == deliverTime) found = true;
00151 }
00152
00153 if(!found){
00154 InterconnectDeliverQueueEvent* event =
00155 new InterconnectDeliverQueueEvent(this);
00156 event->schedule(deliverTime);
00157 deliverEvents.push_back(event);
00158 }
00159 }
00160
00161 void
00162 Butterfly::arbitrate(Tick cycle){
00163
00164
00165 for(int i=0;i<butterflyStatus.size();i++) butterflyStatus[i] = false;
00166
00167 list<InterconnectRequest* > notGrantedReqs;
00168 Tick legalRequestTime = cycle - arbitrationDelay;
00169
00170 list<InterconnectRequest*>::iterator pos;
00171 while(!requestQueue.empty()){
00172 if(requestQueue.front()->time <= legalRequestTime){
00173
00174 int toInterface = getDestinationId(requestQueue.front()->fromID);
00175 if(toInterface == -1){
00176
00177 delete requestQueue.front();
00178 requestQueue.pop_front();
00179 continue;
00180 }
00181
00182 if(setChannelsOccupied(
00183 requestQueue.front()->fromID,
00184 toInterface)){
00185
00186
00187 arbitratedRequests++;
00188 totalArbQueueCycles +=
00189 (cycle - requestQueue.front()->time) - arbitrationDelay;
00190 totalArbitrationCycles += arbitrationDelay;
00191
00192
00193 allInterfaces[requestQueue.front()->fromID]->grantData();
00194 delete requestQueue.front();
00195 requestQueue.pop_front();
00196
00197 }
00198 else{
00199 notGrantedReqs.push_back(requestQueue.front());
00200 requestQueue.pop_front();
00201 }
00202
00203 }
00204 else{
00205 notGrantedReqs.push_back(requestQueue.front());
00206 requestQueue.pop_front();
00207 }
00208 }
00209
00210 if(!notGrantedReqs.empty()){
00211
00212
00213 assert(requestQueue.empty());
00214 requestQueue.splice(requestQueue.begin(), notGrantedReqs);
00215
00216 if(requestQueue.front()->time <= cycle){
00217 scheduleArbitrationEvent(cycle+1);
00218 }
00219 else{
00220 scheduleArbitrationEvent(
00221 requestQueue.front()->time + arbitrationDelay);
00222 }
00223 }
00224
00225 assert(butterflyStatus.size() == channelUsage.size());
00226 for(int i=0;i<butterflyStatus.size();i++){
00227 if(butterflyStatus[i]) channelUsage[i]++;
00228 }
00229 }
00230
00231 bool
00232 Butterfly::setChannelsOccupied(int fromInterfaceID, int toInterfaceID){
00233
00234 assert(fromInterfaceID >= 0 && toInterfaceID >= 0);
00235
00236
00237 int fromNodeId = (allInterfaces[fromInterfaceID]->isMaster() ?
00238 cpuIDtoNode[interconnectIDToProcessorIDMap[fromInterfaceID]]
00239 : l2IDtoNode[interconnectIDToL2IDMap[fromInterfaceID]]);
00240
00241 int toNodeId = (allInterfaces[toInterfaceID]->isMaster() ?
00242 cpuIDtoNode[interconnectIDToProcessorIDMap[toInterfaceID]]
00243 : l2IDtoNode[interconnectIDToL2IDMap[toInterfaceID]]);
00244
00245
00246 vector<bool> tmpState = butterflyStatus;
00247
00248 int atSwitch = -1;
00249 for(int i=0;i<hopCount;i++){
00250
00251 if(i == 0){
00252
00253 if(butterflyStatus[fromNodeId]){
00254 butterflyStatus = tmpState;
00255 return false;
00256 }
00257
00258 butterflyStatus[fromNodeId] = true;
00259
00260 atSwitch = fromNodeId / radix;
00261
00262 }
00263 else if(i == hopCount-1){
00264 int lastStageChanID = (chanBetweenStages * i) + toNodeId;
00265 if(butterflyStatus[lastStageChanID]){
00266 butterflyStatus = tmpState;
00267 return false;
00268 }
00269 butterflyStatus[lastStageChanID] = true;
00270 }
00271 else{
00272
00273 int useChannelNum = -1;
00274 if((toNodeId & (1 << (stages - i))) > 0) useChannelNum = 1;
00275 else useChannelNum = 0;
00276 int channelID = (atSwitch * 2) + useChannelNum;
00277
00278 int offset = 1 << (stages - i - 1);
00279 int nextSwitch = -1;
00280 if((atSwitch & offset) == 0 && useChannelNum == 1){
00281 nextSwitch = atSwitch + offset;
00282 }
00283 else if((atSwitch & offset) > 0 && useChannelNum == 0){
00284 nextSwitch = atSwitch - offset;
00285 }
00286 else{
00287 nextSwitch = atSwitch;
00288 }
00289
00290 int stageOffset = chanBetweenStages * i;
00291 if(butterflyStatus[stageOffset + channelID]){
00292 butterflyStatus = tmpState;
00293 return false;
00294 }
00295
00296 butterflyStatus[stageOffset + channelID] = true;
00297
00298 atSwitch = nextSwitch;
00299 }
00300 }
00301 return true;
00302 }
00303
00304 void
00305 Butterfly::deliver(MemReqPtr& req, Tick cycle, int toID, int fromID){
00306
00307 assert(!blocked);
00308
00309 assert(!req);
00310 assert(toID == -1);
00311 assert(fromID == -1);
00312
00313 assert(isSorted(&deliverQueue));
00314
00315 int butterflyTransDelay = stages*switchDelay + hopCount*transferDelay;
00316 Tick legalGrantTime = cycle - butterflyTransDelay;
00317
00318
00319
00320 while(!deliverQueue.empty()){
00321 InterconnectDelivery* delivery = deliverQueue.front();
00322
00323
00324
00325 if(delivery->grantTime > legalGrantTime) break;
00326
00327 deliverQueue.pop_front();
00328
00329
00330 sentRequests++;
00331 int curCpuId = delivery->req->xc->cpu->params->cpu_id;
00332 int queueCycles = (cycle - delivery->grantTime) - butterflyTransDelay;
00333
00334 totalTransQueueCycles += queueCycles;
00335 totalTransferCycles += butterflyTransDelay;
00336 perCpuTotalTransQueueCycles[curCpuId] += queueCycles;
00337 perCpuTotalTransferCycles[curCpuId] += butterflyTransDelay;
00338
00339
00340 int retval = BA_NO_RESULT;
00341 if(allInterfaces[delivery->toID]->isMaster()){
00342 allInterfaces[delivery->toID]->deliver(delivery->req);
00343 }
00344 else{
00345 retval = allInterfaces[delivery->toID]->access(delivery->req);
00346 }
00347
00348 delete delivery;
00349
00350
00351 if(retval == BA_BLOCKED) break;
00352 }
00353 }
00354
00355 void
00356 Butterfly::setBlocked(int fromInterface){
00357 if(blocked) warn("blocking on a second cause");
00358 blocked = true;
00359 waitingFor = fromInterface;
00360 blockedAt = curTick;
00361 numSetBlocked++;
00362
00363 blockedInterfaces.push_back(fromInterface);
00364
00365 for(int i=0;i<arbitrationEvents.size();++i){
00366 if(arbitrationEvents[i]->scheduled()){
00367 arbitrationEvents[i]->deschedule();
00368 }
00369 delete arbitrationEvents[i];
00370 }
00371 arbitrationEvents.clear();
00372
00373 for(int i=0;i<deliverEvents.size();++i){
00374 if(deliverEvents[i]->scheduled()){
00375 deliverEvents[i]->deschedule();
00376 }
00377
00378 delete deliverEvents[i];
00379 }
00380 deliverEvents.clear();
00381 }
00382
00383 void
00384 Butterfly::clearBlocked(int fromInterface){
00385 assert(blocked);
00386 assert(blockedAt > -1);
00387
00388 int hitIndex = -1;
00389 int hitCount = 0;
00390 for(int i=0;i<blockedInterfaces.size();i++){
00391 if(blockedInterfaces[i] == fromInterface){
00392 hitIndex = i;
00393 hitCount++;
00394 }
00395 }
00396 assert(hitCount == 1 && hitIndex > -1);
00397 blockedInterfaces.erase(blockedInterfaces.begin()+hitIndex);
00398
00399 if(blockedInterfaces.empty()){
00400
00401 blocked = false;
00402 numClearBlocked++;
00403
00404 assert(arbitrationEvents.empty());
00405 if(!requestQueue.empty()){
00406
00407
00408 Tick firstReq = (requestQueue.front())->time;
00409
00410 InterconnectArbitrationEvent* event =
00411 new InterconnectArbitrationEvent(this);
00412 arbitrationEvents.push_back(event);
00413
00414 if((firstReq + arbitrationDelay) <= curTick){
00415 event->schedule(curTick);
00416 }
00417 else{
00418 event->schedule(firstReq + arbitrationDelay);
00419 }
00420 }
00421
00422 assert(deliverEvents.empty());
00423 if(!deliverQueue.empty()){
00424
00425
00426 Tick firstGrant = (deliverQueue.front())->grantTime;
00427
00428 InterconnectDeliverQueueEvent* event =
00429 new InterconnectDeliverQueueEvent(this);
00430 deliverEvents.push_back(event);
00431
00432 if((firstGrant + transferDelay) <= curTick){
00433 event->schedule(curTick);
00434 }
00435 else event->schedule(firstGrant + transferDelay);
00436 }
00437
00438 blockedAt = -1;
00439 }
00440 }
00441
00442 int
00443 Butterfly::getChannelCount(){
00444 return hopCount * chanBetweenStages;
00445 }
00446
00447 vector<int>
00448 Butterfly::getChannelSample(){
00449 vector<int> copy = channelUsage;
00450 assert(channelUsage.size() == getChannelCount());
00451 for(int i=0;i<channelUsage.size();i++) channelUsage[i] = 0;
00452 return copy;
00453 }
00454
00455 void
00456 Butterfly::writeChannelDecriptor(std::ofstream &stream){
00457 stream << "Interfaces:\n";
00458 for(int i=0;i<allInterfaces.size();i++){
00459 stream << "Interface " << i
00460 << " (" << allInterfaces[i]->getCacheName() << "): "
00461 << " mapped to node id "
00462 << (allInterfaces[i]->isMaster() ?
00463 cpuIDtoNode[interconnectIDToProcessorIDMap[i]] :
00464 l2IDtoNode[interconnectIDToL2IDMap[i]] )
00465 << "\n";
00466 }
00467
00468 stream << "\nChannels:\n";
00469
00470 int chanSet = 0;
00471 for(int i=0;i<(hopCount * chanBetweenStages);i++){
00472
00473 if(i != 0 && i % chanBetweenStages == 0){
00474 chanSet++;
00475 stream << "\n";
00476 }
00477
00478 stream << "Channel ID " << i << ": In set "
00479 << chanSet << ", id in set "
00480 << (i % chanBetweenStages) << "\n";
00481 }
00482 }
00483
00484 void
00485 Butterfly::printChannelStatus(){
00486
00487 cout << "ID: ";
00488 for(int i=0;i<chanBetweenStages;i++){
00489 if(i<=10) cout << " " << i << " ";
00490 else cout << " " << i << " ";
00491 }
00492 cout << "\n";
00493
00494 int chanGroup = 0;
00495 cout << "Channel Group " << chanGroup << ": ";
00496 for(int i=0;i<butterflyStatus.size();i++){
00497 cout << (butterflyStatus[i] ? " true" : "false") << " ";
00498 if(i != 1 && (i+1) % chanBetweenStages == 0){
00499 chanGroup++;
00500 cout << "\n";
00501 if(i != butterflyStatus.size()-1){
00502 cout << "Channel Group " << chanGroup << ": ";
00503 }
00504 }
00505 }
00506 }
00507
00508 void
00509 Butterfly::scheduleArbitrationEvent(Tick candidateTime){
00510
00511 int found = false;
00512 for(int i=0;i<arbitrationEvents.size();i++){
00513 if(arbitrationEvents[i]->when() == candidateTime) found = true;
00514 }
00515
00516 if(!found){
00517 InterconnectArbitrationEvent* event =
00518 new InterconnectArbitrationEvent(this);
00519 event->schedule(candidateTime);
00520 arbitrationEvents.push_back(event);
00521 }
00522 }
00523
00524 int
00525 Butterfly::getDestinationId(int fromID){
00526
00527 if(allInterfaces[fromID]->isMaster()){
00528
00529 pair<Addr,int> tmp = allInterfaces[fromID]->getTargetAddr();
00530 Addr targetAddr = tmp.first;
00531 int toInterfaceId = tmp.second;
00532
00533
00534 if(targetAddr == 0) return -1;
00535
00536
00537 if(toInterfaceId != -1) return toInterfaceId;
00538
00539 return getTarget(targetAddr);
00540 }
00541
00542 int retID = allInterfaces[fromID]->getTargetId();
00543 assert(retID != -1);
00544 return retID;
00545 }
00546
00547
00548 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00549
00550 BEGIN_DECLARE_SIM_OBJECT_PARAMS(Butterfly)
00551 Param<int> width;
00552 Param<int> clock;
00553 Param<int> transferDelay;
00554 Param<int> arbitrationDelay;
00555 Param<int> cpu_count;
00556 SimObjectParam<HierParams *> hier;
00557 Param<int> switch_delay;
00558 Param<int> radix;
00559 Param<int> banks;
00560 END_DECLARE_SIM_OBJECT_PARAMS(Butterfly)
00561
00562 BEGIN_INIT_SIM_OBJECT_PARAMS(Butterfly)
00563 INIT_PARAM(width, "the width of the crossbar transmission channels"),
00564 INIT_PARAM(clock, "butterfly clock"),
00565 INIT_PARAM(transferDelay, "butterfly transfer delay in CPU cycles"),
00566 INIT_PARAM(arbitrationDelay, "butterfly arbitration delay in CPU cycles"),
00567 INIT_PARAM(cpu_count, "the number of CPUs in the system"),
00568 INIT_PARAM_DFLT(hier,
00569 "Hierarchy global variables",
00570 &defaultHierParams),
00571 INIT_PARAM_DFLT(switch_delay,
00572 "The delay of a switch in CPU cycles",
00573 1),
00574 INIT_PARAM(radix, "The switching-degree of each switch"),
00575 INIT_PARAM(banks, "the number of last-level cache banks")
00576 END_INIT_SIM_OBJECT_PARAMS(Butterfly)
00577
00578 CREATE_SIM_OBJECT(Butterfly)
00579 {
00580 return new Butterfly(getInstanceName(),
00581 width,
00582 clock,
00583 transferDelay,
00584 arbitrationDelay,
00585 cpu_count,
00586 hier,
00587 switch_delay,
00588 radix,
00589 banks);
00590 }
00591
00592 REGISTER_SIM_OBJECT("Butterfly", Butterfly)
00593
00594 #endif //DOXYGEN_SHOULD_SKIP_THIS
00595