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
00014
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
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
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
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
00095
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
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
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
00146
00147
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
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
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
00219 if(targetAddr == 0) return -1;
00220
00221
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
00252 if(doProfiling){
00253 if(busIsUsed){
00254
00255 channelUseCycles[allInterfaces.size()] += transferDelay;
00256 }
00257 else{
00258
00259
00260
00261 channelUseCycles[fromID] += 1;
00262 channelUseCycles[toID] += 1;
00263 }
00264 }
00265
00266 deliverQueue.push_back(new InterconnectDelivery(time, fromID, toID, req));
00267
00268
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
00299
00300 while(!deliverQueue.empty()){
00301 InterconnectDelivery* delivery = deliverQueue.front();
00302
00303
00304
00305 if(delivery->grantTime > legalGrantTime) break;
00306
00307 deliverQueue.pop_front();
00308
00309
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
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
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
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