butterfly.cc

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     // compute topology utility vars
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     /* check if we need to schedule a deliver event */
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     // reset internal state
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                 // null request, remove
00177                 delete requestQueue.front();
00178                 requestQueue.pop_front();
00179                 continue;
00180             }
00181             
00182             if(setChannelsOccupied(
00183                     requestQueue.front()->fromID,
00184                     toInterface)){
00185                 
00186                 // update statistics
00187                 arbitratedRequests++;
00188                 totalArbQueueCycles += 
00189                     (cycle - requestQueue.front()->time) - arbitrationDelay;
00190                 totalArbitrationCycles += arbitrationDelay;
00191                 
00192                 // grant access
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         // there where requests we could not issue
00212         // put them back in the queue and schedule new arb event
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     // translate into butterfly node IDs
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     // store old state in case we can't grant the request
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     /* attempt to deliver as many requests as possible */
00319     /* since the queue is sorted, starvation is not possible */
00320     while(!deliverQueue.empty()){
00321         InterconnectDelivery* delivery = deliverQueue.front();
00322         
00323         /* check if this grant has experienced the proper delay */
00324         /* since the requests are sorted, we know that all other are later */
00325         if(delivery->grantTime > legalGrantTime) break;
00326         
00327         deliverQueue.pop_front();
00328         
00329         /* update statistics */
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         /* if the cache returns blocked we cannot deliver any more data */
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             /* schedule new arbitration event */
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             /* schedule new deliver event */
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         // The request was a null request, remove
00534         if(targetAddr == 0) return -1;
00535         
00536         // we allready know the to interface id if it's an L1 to L1 transfer
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 

Generated on Tue Jun 5 12:55:20 2007 for M5InterconnectExtensions by  doxygen 1.4.7