crossbar.cc

00001 
00002 #include "sim/builder.hh"
00003 #include "crossbar.hh"
00004         
00005 using namespace std;
00006 
00007 void
00008 Crossbar::request(Tick time, int fromID){
00009     
00010     requests++;
00011     
00012     if(isFirstRequest){
00013         //NOTE: This can not be initalised before alle interfaces has registered
00014         //      Consequently, doing it when the first request arrives is safe
00015         for(int i=0;i<allInterfaces.size();i++){
00016             requestQueues.push_back(new list<InterconnectRequest*>);
00017         }
00018         
00019         isFirstRequest = false;
00020     }
00021     
00022     insertIntoList(requestQueues[fromID], time, fromID);
00023     
00024     if(!blocked) scheduleArbitrationEvent(time + arbitrationDelay);
00025 
00026 }
00027 
00028 void
00029 Crossbar::insertIntoList(list<InterconnectRequest* >* inList,
00030                          Tick reqTime, 
00031                          int fromID){
00032 
00033     if(inList->empty() || inList->back()->time <= reqTime){
00034         // fast common case;
00035         inList->push_back(new InterconnectRequest(reqTime, fromID));
00036     }
00037     else{
00038         list<InterconnectRequest*>::iterator pos;
00039         for(pos = inList->begin();
00040             pos != inList->end();
00041             pos++){
00042                 if((*pos)->time > reqTime) break;
00043         }
00044         inList->insert(pos, new InterconnectRequest(reqTime, fromID));
00045     }
00046     
00047 #ifdef DEBUG_CROSSBAR
00048     /* Make sure that the queues are sorted */
00049     for(int i=0;i<requestQueues.size();i++){
00050         assert(isSorted(requestQueues[i]));
00051     }
00052 #endif //DEBUG_CROSSBAR
00053 }
00054 
00055 void
00056 Crossbar::scheduleArbitrationEvent(Tick candidateTime){
00057     
00058     int found = false;
00059     for(int i=0;i<arbitrationEvents.size();i++){
00060         if(arbitrationEvents[i]->when() == candidateTime) found = true;
00061     }
00062     
00063     if(!found){
00064         InterconnectArbitrationEvent* event = 
00065                 new InterconnectArbitrationEvent(this);
00066         event->schedule(candidateTime);
00067         arbitrationEvents.push_back(event);
00068     }
00069 }
00070 
00071 void
00072 Crossbar::arbitrate(Tick cycle){
00073     
00074     assert(!blocked);
00075     
00076     Tick legalRequestTime = cycle - arbitrationDelay;
00077     
00078     /* create storage for the arbitraion process */
00079     vector<bool> deliverBusy(allInterfaces.size(), false);
00080     vector<bool> senderBusy(allInterfaces.size(), false);
00081     bool toOtherL1Busy = false;
00082     
00083     if(cycle < nextBusFreeTime) toOtherL1Busy = true;
00084     
00085     
00086     vector<list<InterconnectRequest*> > 
00087             delayedRequests(allInterfaces.size());
00088     for(int i=0;i<delayedRequests.size();i++){
00089         delayedRequests[i] = list<InterconnectRequest*>();
00090     }
00091     
00092     while(moreRequestsAvailable()){
00093         
00094         /* start with the oldest request, regardless of which queue it is in
00095            Consequently, starvation is avoided */
00096         int smallestId = -1;
00097         Tick smallest = TICK_T_MAX;
00098         for(int i=0;i<requestQueues.size();i++){
00099             if(!requestQueues[i]->empty() 
00100                 && requestQueues[i]->front()->time < smallest){
00101                 smallest = requestQueues[i]->front()->time;
00102                 smallestId = i;
00103             }
00104         }
00105         assert(smallestId >= 0);
00106         
00107         InterconnectRequest* tempReq = requestQueues[smallestId]->front();
00108         requestQueues[smallestId]->pop_front();
00109         
00110         if(tempReq->time <= legalRequestTime){
00111         
00112             int toID = getDestinationId(tempReq->fromID);
00113             
00114             if(toID == -1){
00115                 /* this was a null request, remove it and move on */
00116                 delete tempReq;
00117                 continue;
00118             }
00119             
00120             if(allInterfaces[toID]->isMaster()
00121                && allInterfaces[tempReq->fromID]->isMaster()){
00122                 
00123                 if(toOtherL1Busy){
00124                     delayedRequests[tempReq->fromID].push_back(tempReq);
00125                     continue;
00126                 }
00127                 else{
00128                     toOtherL1Busy = true;
00129                     nextBusFreeTime = (cycle + arbitrationDelay);
00130                     
00131                     /* update statistics */
00132                     arbitratedRequests++;
00133                     totalArbQueueCycles += 
00134                             (cycle - tempReq->time) - arbitrationDelay;
00135                     totalArbitrationCycles += arbitrationDelay;
00136                     
00137                     allInterfaces[tempReq->fromID]->grantData();
00138                     delete tempReq;
00139                     
00140                     continue;
00141                 }
00142             }
00143             
00144             if(!deliverBusy[toID] && !senderBusy[tempReq->fromID]){
00145                 /* request can be delivered*/
00146                 
00147                 /* update statistics */
00148                 arbitratedRequests++;
00149                 totalArbQueueCycles += 
00150                         (cycle - tempReq->time) - arbitrationDelay;
00151                 totalArbitrationCycles += arbitrationDelay;
00152                 
00153                 allInterfaces[tempReq->fromID]->grantData();
00154                 delete tempReq;
00155                 
00156                 
00157                 deliverBusy[toID] = true;
00158                 senderBusy[tempReq->fromID] = true;
00159                 continue;
00160             }
00161         }
00162         delayedRequests[tempReq->fromID].push_back(tempReq);
00163     }
00164     
00165     /* put not granted requests back in the request queues */
00166     assert(requestQueues.size() == delayedRequests.size());
00167     for(int i=0;i<requestQueues.size();i++){
00168         assert(requestQueues[i]->empty());
00169         (*requestQueues[i]) = delayedRequests[i];
00170     }
00171     
00172     /* check if we need to schedule new arbitration events */
00173     Tick nextArbTime = TICK_T_MAX;
00174     bool addArbEvent = false;
00175     for(int i=0;i<requestQueues.size();i++){
00176         if(!requestQueues[i]->empty()){
00177             InterconnectRequest* first = requestQueues[i]->front();
00178             Tick candidateTime = first->time + arbitrationDelay;
00179             if(candidateTime <= cycle){
00180                 if((cycle + 1) < nextArbTime){
00181                     addArbEvent = true;
00182                     nextArbTime = cycle + 1;
00183                 }
00184             }
00185             else{
00186                 if(candidateTime < nextArbTime){
00187                     addArbEvent = true;
00188                     nextArbTime = candidateTime;
00189                 }
00190             }
00191         }
00192     }
00193     
00194     if(addArbEvent){
00195         assert(nextArbTime != TICK_T_MAX);
00196         scheduleArbitrationEvent(nextArbTime);
00197     }
00198 }
00199 
00200 bool
00201 Crossbar::moreRequestsAvailable(){
00202     bool moreReqs = false;
00203     for(int i=0;i<requestQueues.size();i++){
00204         if(!requestQueues[i]->empty()) moreReqs = true;
00205     }
00206     return moreReqs;
00207 }
00208 
00209 int
00210 Crossbar::getDestinationId(int fromID){
00211     
00212     if(allInterfaces[fromID]->isMaster()){
00213         
00214         pair<Addr,int> tmp = allInterfaces[fromID]->getTargetAddr();
00215         Addr targetAddr = tmp.first;
00216         int toInterfaceId = tmp.second;
00217         
00218         // The request was a null request, remove
00219         if(targetAddr == 0) return -1;
00220         
00221         // we allready know the to interface id if it's an L1 to L1 transfer
00222         if(toInterfaceId != -1) return toInterfaceId;
00223         
00224         return getTarget(targetAddr);
00225     }
00226     
00227     int retID = allInterfaces[fromID]->getTargetId();
00228     assert(retID != -1);
00229     return retID;
00230 }
00231 
00232 void
00233 Crossbar::send(MemReqPtr& req, Tick time, int fromID){
00234     
00235     assert(!blocked);
00236     assert((req->size / width) <= 1);
00237     
00238     int toID = -1;
00239     bool busIsUsed = false;
00240     if(allInterfaces[fromID]->isMaster() && req->toInterfaceID != -1){
00241         busIsUsed = true;
00242         toID = req->toInterfaceID;
00243     }
00244     else if(allInterfaces[fromID]->isMaster()){
00245         toID = getTarget(req->paddr);
00246     }
00247     else{
00248         toID = req->fromInterfaceID;
00249     }
00250     
00251     //update profile stats
00252     if(doProfiling){
00253         if(busIsUsed){
00254             // the coherence bus is not pipelined
00255             channelUseCycles[allInterfaces.size()] += transferDelay;
00256         }
00257         else{
00258             // regular pipelined crossbar channels used
00259             // one pipeline slot is allocated in both sender
00260             // and recievers channel
00261             channelUseCycles[fromID] += 1;
00262             channelUseCycles[toID] += 1;
00263         }
00264     }
00265     
00266     deliverQueue.push_back(new InterconnectDelivery(time, fromID, toID, req));
00267     
00268     /* check if we need to schedule a deliver event */
00269     Tick deliverTime = time + transferDelay;
00270     bool found = false;
00271     for(int i=0;i<deliverEvents.size();i++){
00272         if(deliverEvents[i]->when() == deliverTime) found = true;
00273     }
00274     
00275     if(!found){
00276         InterconnectDeliverQueueEvent* event = 
00277                 new InterconnectDeliverQueueEvent(this);
00278         event->schedule(deliverTime);
00279         deliverEvents.push_back(event);
00280     }
00281 }
00282 
00283 
00284 void
00285 Crossbar::deliver(MemReqPtr& req, Tick cycle, int toID, int fromID){
00286     assert(!blocked);
00287     
00288     assert(!req);
00289     assert(toID == -1);
00290     assert(fromID == -1);
00291     
00292 #ifdef DEBUG_CROSSBAR
00293     assert(isSorted(&deliverQueue));
00294 #endif //DEBUG_CROSSBAR
00295     
00296     Tick legalGrantTime = cycle - transferDelay;
00297 
00298     /* attempt to deliver as many requests as possible */
00299     /* since the queue is sorted, starvation is not possible */
00300     while(!deliverQueue.empty()){
00301         InterconnectDelivery* delivery = deliverQueue.front();
00302         
00303         /* check if this grant has experienced the proper delay */
00304         /* since the requests are sorted, we know that all other are later */
00305         if(delivery->grantTime > legalGrantTime) break;
00306         
00307         deliverQueue.pop_front();
00308         
00309         /* update statistics */
00310         sentRequests++;
00311         int curCpuId = delivery->req->xc->cpu->params->cpu_id;
00312         int queueCycles = (cycle - delivery->grantTime) - transferDelay;
00313         
00314         totalTransQueueCycles += queueCycles;
00315         totalTransferCycles += transferDelay;
00316         perCpuTotalTransQueueCycles[curCpuId] += queueCycles;
00317         perCpuTotalTransferCycles[curCpuId] += transferDelay;
00318         
00319         
00320         int retval = BA_NO_RESULT;
00321         if(allInterfaces[delivery->toID]->isMaster()){
00322             allInterfaces[delivery->toID]->deliver(delivery->req);
00323         }
00324         else{
00325             retval = allInterfaces[delivery->toID]->access(delivery->req);
00326         }
00327         
00328         delete delivery;
00329         
00330         /* if the cache returns blocked we cannot deliver any more data */
00331         if(retval == BA_BLOCKED) break;
00332     }
00333 }
00334 
00335 void
00336 Crossbar::setBlocked(int fromInterface){
00337     
00338     if(blocked) warn("blocking on a second cause");
00339     blocked = true;
00340     waitingFor = fromInterface;
00341     blockedAt = curTick;
00342     numSetBlocked++;
00343     
00344     blockedInterfaces.push_back(fromInterface);
00345     
00346     for(int i=0;i<arbitrationEvents.size();++i){
00347         if(arbitrationEvents[i]->scheduled()){
00348             arbitrationEvents[i]->deschedule();
00349         }
00350         delete arbitrationEvents[i];
00351     }
00352     arbitrationEvents.clear();
00353     
00354     for(int i=0;i<deliverEvents.size();++i){
00355         if(deliverEvents[i]->scheduled()){
00356             deliverEvents[i]->deschedule();
00357         }
00358         
00359         delete deliverEvents[i];
00360     }
00361     deliverEvents.clear();
00362 
00363 }
00364 
00365 void
00366 Crossbar::clearBlocked(int fromInterface){
00367     
00368     assert(blocked);
00369     assert(blockedAt > -1);
00370         
00371     int hitIndex = -1;
00372     int hitCount = 0;
00373     for(int i=0;i<blockedInterfaces.size();i++){
00374         if(blockedInterfaces[i] == fromInterface){
00375             hitIndex = i;
00376             hitCount++;
00377         }
00378     }
00379     assert(hitCount == 1 && hitIndex > -1);
00380     blockedInterfaces.erase(blockedInterfaces.begin()+hitIndex);
00381     
00382     if(blockedInterfaces.empty()){
00383         
00384         blocked = false;
00385         numClearBlocked++;
00386         
00387         assert(arbitrationEvents.empty());
00388         if(moreRequestsAvailable()){
00389             
00390             /* schedule new arbitration event */
00391             Tick firstReq = TICK_T_MAX;
00392             for(int i=0;i<requestQueues.size();i++){
00393                 if(!requestQueues[i]->empty() 
00394                     && requestQueues[i]->front()->time < firstReq){
00395                     firstReq = requestQueues[i]->front()->time;
00396                 }
00397             }
00398             assert(firstReq != TICK_T_MAX);
00399             
00400             InterconnectArbitrationEvent* event = 
00401                     new InterconnectArbitrationEvent(this);
00402             arbitrationEvents.push_back(event);
00403             
00404             if(firstReq <= curTick) event->schedule(curTick);
00405             else event->schedule(firstReq);
00406         }
00407         
00408         assert(deliverEvents.empty());
00409         if(!deliverQueue.empty()){
00410             
00411             /* schedule new deliver event */
00412             Tick firstGrant = (deliverQueue.front())->grantTime;
00413             
00414             InterconnectDeliverQueueEvent* event = 
00415                     new InterconnectDeliverQueueEvent(this);
00416             deliverEvents.push_back(event);
00417             
00418             if(firstGrant <= curTick) event->schedule(curTick);
00419             else event->schedule(firstGrant);
00420         }
00421         blockedAt = -1;
00422     }
00423     
00424     
00425 }
00426 
00427 vector<int>
00428 Crossbar::getChannelSample(){
00429     
00430     if(!doProfiling) doProfiling = true;
00431     
00432     std::vector<int> retval(channelUseCycles);
00433     
00434     for(int i=0;i<channelUseCycles.size();i++){
00435         channelUseCycles[i] = 0;
00436     }
00437     
00438     return retval;
00439 }
00440 
00441 void
00442 Crossbar::writeChannelDecriptor(std::ofstream &stream){
00443     
00444     for(int i=0;i<allInterfaces.size();i++){
00445         stream << "Channel " << i << ": " 
00446                << allInterfaces[i]->getCacheName() << "\n";
00447     }
00448     stream << "Channel " << allInterfaces.size() << ": Coherence bus\n";
00449 }
00450 
00451     
00452 #ifdef DEBUG_CROSSBAR
00453 
00454 void
00455 Crossbar::printRequests(){
00456     for(int i=0;i<requestQueues.size();i++){
00457         cout << i << ": ";
00458         for(list<InterconnectRequest*>::iterator j=requestQueues[i]->begin();
00459             j != requestQueues[i]->end();
00460             j++){
00461                 InterconnectRequest* current = *j;
00462                 cout << "(" 
00463                         << current->fromID 
00464                         << ", " 
00465                         << current->time 
00466                         << ") ";
00467         }
00468         cout << "\n";
00469     }
00470     cout << "\n";
00471 }
00472 
00473 #endif //DEBUG_CROSSBAR
00474 
00475 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00476 
00477 BEGIN_DECLARE_SIM_OBJECT_PARAMS(Crossbar)
00478     Param<int> width;
00479     Param<int> clock;
00480     Param<int> transferDelay;
00481     Param<int> arbitrationDelay;
00482     Param<int> cpu_count;
00483     SimObjectParam<HierParams *> hier;
00484 END_DECLARE_SIM_OBJECT_PARAMS(Crossbar)
00485 
00486 BEGIN_INIT_SIM_OBJECT_PARAMS(Crossbar)
00487     INIT_PARAM(width, "the width of the crossbar transmission channels"),
00488     INIT_PARAM(clock, "crossbar clock"),
00489     INIT_PARAM(transferDelay, "crossbar transfer delay in CPU cycles"),
00490     INIT_PARAM(arbitrationDelay, "crossbar arbitration delay in CPU cycles"),
00491     INIT_PARAM(cpu_count, "the number of CPUs in the system"),
00492     INIT_PARAM_DFLT(hier,
00493                     "Hierarchy global variables",
00494                     &defaultHierParams)
00495 END_INIT_SIM_OBJECT_PARAMS(Crossbar)
00496 
00497 CREATE_SIM_OBJECT(Crossbar)
00498 {
00499     return new Crossbar(getInstanceName(),
00500                                  width,
00501                                  clock,
00502                                  transferDelay,
00503                                  arbitrationDelay,
00504                                  cpu_count,
00505                                  hier);
00506 }
00507 
00508 REGISTER_SIM_OBJECT("Crossbar", Crossbar)
00509 
00510 #endif //DOXYGEN_SHOULD_SKIP_THIS

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