SDF.cpp

00001 #include "SDF.h"
00002 
00003 /*set the input to a ring buffer pointed to by buf, the input node will read input from this ring buffer*/
00004 void INode::setInput(RingBuffer *buf){
00005   input=buf;
00006 }
00007 
00008 /*each time inode executes, reading one sample from input ring buffer, and put this data onto all the outgoing edges*/
00009 void INode::execute(){
00010   int inputSample = input->next();
00011   for(int i=0; i<(int)outbounds.size(); i++){
00012     outbounds[i]->putData(inputSample);
00013   }
00014 }
00015 
00016 /*display function*/
00017 void INode::display()const{
00018   printf("INode id=%d type=%d ", id, type);
00019   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00020   printf("\r\n");
00021 }
00022 
00023 /*set the output to a ring buffer pointed to by buf, the output node will write output samples into this buf*/
00024 void ONode::setOutput(RingBuffer *buf){
00025   output=buf;
00026 }
00027 
00028 /*each time onode executes, reading one sample from inbound FIFO and write this sample to ring buffer; also compute checksum*/
00029 void ONode::execute(){
00030   int sampleOut=inbound->getData();
00031   checksum ^= sampleOut;
00032   output->insert(sampleOut);
00033 }
00034 
00035 /*display function*/
00036 void ONode::display()const{
00037   printf("ONode id=%d type=%d %d\r\n", id, type, inbound->getId());
00038 }
00039 
00040 /*each time anode executes, reading operand1 from one inbound FIFO op1, reading operand2 from the other inbound FIFO op2,
00041  compute the sum of the two and put this result onto all the outbound FIFOs*/
00042 void ANode::execute(){
00043   int a = op1->getData(), b = op2->getData();
00044   for(int i=0; i<(int)outbounds.size(); i++){
00045     outbounds[i]->putData(a+b);
00046   }
00047 }
00048 
00049 /*display function*/
00050 void ANode::display()const{
00051   printf("ANode id=%d type=%d %d %d ", id, type, op1->getId(), op2->getId());
00052   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00053   printf("\r\n");
00054 }
00055 
00056 /*each time anode executes, reading operand1 from one inbound FIFO op1, reading operand2 from the other inbound FIFO op2,
00057  compute the difference of the two and put this result onto all the outbound FIFOs*/
00058 void SNode::execute(){
00059   int a = op1->getData(), b = op2->getData();
00060   for(int i=0; i<(int)outbounds.size(); i++){
00061     outbounds[i]->putData(a-b);
00062   }
00063 }
00064 
00065 /*display function*/
00066 void SNode::display()const{
00067   printf("SNode id=%d type=%d %d %d ", id, type, op1->getId(), op2->getId());
00068   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00069   printf("\r\n");
00070 }
00071 
00072 /*each time mnode executes, reading a sample from inbound FIFO, multiply it by c and divide by d, put the result onto all
00073  the outbound FIFOs*/
00074 void MNode::execute(){
00075   int a = inbound->getData();
00076   for(int i=0; i<(int)outbounds.size(); i++){
00077     outbounds[i]->putData(a*c/d);
00078   }
00079 }
00080 
00081 /*display function*/
00082 void MNode::display()const{
00083   printf("MNode id=%d type=%d c=%d d=%d %d ", id, type, c, d, inbound->getId());
00084   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00085   printf("\r\n");
00086 }
00087 
00088 /*each time dnode executes, read numOfSamples samples from inbound FIFO, put the first sample (sample 0) onto all the outbound FIFOs*/
00089 void DNode::execute(){
00090   for(int i=0; i<numOfSamples; i++){
00091     int d = inbound->getData();
00092     if(i==0){
00093       for(int j=0; j<(int)outbounds.size(); j++)outbounds[j]->putData(d);
00094     }
00095   }
00096 }
00097 
00098 /*display function*/
00099 void DNode::display()const{
00100   printf("DNode id=%d type=%d n=%d %d ", id, type, numOfSamples, inbound->getId());
00101   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00102   printf("\r\n");
00103 }
00104 
00105 /*each time unode executes, read a sample from inbound FIFO, duplicate numOfCopies copies, put all those copies onto outbound FIFOs*/
00106 void UNode::execute(){
00107   int a = inbound->getData();
00108   for(int i=0; i<(int)outbounds.size(); i++){
00109     for(int j=0; j<numOfCopies; j++){outbounds[i]->putData(a);}
00110   }
00111 }
00112 
00113 /*display function*/
00114 void UNode::display()const{
00115   printf("UNode id=%d type=%d n=%d %d ", id, type, numOfCopies, inbound->getId());
00116   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00117   printf("\r\n");
00118 }
00119 
00120 /*each time cnode executes, put the constant onto outbound FIFOs*/
00121 void CNode::execute(){
00122   for(int i=0; i<outbounds.size(); i++){
00123     outbounds[i]->putData(constant);
00124   }
00125 }
00126 
00127 /*display function*/
00128 void CNode::display()const{
00129   printf("CNode id=%d type=%d constant=%d ", id, type, constant);
00130   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00131   printf("\r\n");
00132 }
00133 
00134 /*each time fnode executes, read a sample from inbound FIFO, and put this sample onto outbound FIFOs*/
00135 void FNode::execute(){
00136   int a = inbound->getData();
00137   for(int i=0; i<(int)outbounds.size(); i++){
00138     outbounds[i]->putData(a);
00139   }
00140 }
00141 
00142 /*display function*/
00143 void FNode::display()const{
00144   printf("FNode id=%d type=%d %d ", id, type, inbound->getId());
00145   for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
00146   printf("\r\n");
00147 }
00148 
00149 /*intended for the consumer to use, read one sample from the FIFO, and remove that data*/
00150 int FIFO::getData(){
00151   if(this->fifo.empty()){
00152     error("trying to read from empty FIFO: id=%d...\r\n", this->id);
00153     exit(1);
00154   }
00155   int ret = this->fifo.front();
00156   this->fifo.pop();
00157   return ret;
00158 }
00159 
00160 /*intended for the producer to use, put one sample into the FIFO*/
00161 void FIFO::putData(int d){
00162   this->fifo.push(d);
00163 }
00164 
00165 /*display function*/
00166 void FIFO::display()const{
00167   printf("FIFO id=%d src=%d dst=%d numOfMarkings=%d\r\n", id, src->getId(), dst->getId(), fifo.size());
00168 }
00169 
00170 SDFG::SDFG(char* path, RingBuffer* input, RingBuffer* output):
00171    gin(NULL),gout(NULL),numOfNodes(0),numOfFIFOs(0),scheduleTested(false),schedulable(false), scheduleFound(false)
00172 {
00173     Parser::parseSDFG(path,this);
00174     if(!hasSchedule()){
00175         error("ERROR: CANNOT SCHEDULE\r\n");
00176         exit(1);
00177     }
00178     setInput(input);
00179     setOutput(output);
00180     makeSchedule();
00181 }
00182 
00183 /*destructor, reclaim all the space allocated for nodes and FIFOs*/
00184 SDFG::~SDFG(){
00185   for(int i=0; i<nodes.size(); i++)delete nodes[i];
00186   for(int i=0; i<fifos.size(); i++)delete fifos[i];
00187 }
00188 
00189 /*add a node into the nodes vector, keep the nodes whose id's are arranged in ascending order in the nodes vector;
00190   basically an insertion-sort*/
00191 void SDFG::addNode(SDFNode *node){
00192   if(!node)return;
00193   int i=0;
00194   while(i<nodes.size()&&nodes[i]->getId()<node->getId())i++;
00195   if(i<nodes.size()&&nodes[i]->getId()==node->getId())return;
00196   else if(i>=nodes.size())nodes.push_back(node);
00197   else{
00198     nodes.push_back(NULL);
00199     for(int j=nodes.size()-1;j>i;j--)nodes[j]=nodes[j-1];
00200     nodes[i]=node;
00201   }
00202 }
00203 
00204 /*given an id, if a FIFO with that id exists, return that FIFO; otherwise create a new FIFO, insert the FIFO into
00205   vector fifos, and return that FIFO; also an insertion-sort implementation*/
00206 FIFO* SDFG::getFIFO(int id){
00207   int i=0;
00208   FIFO *fifo=NULL;
00209   while(i<fifos.size()&&fifos[i]->getId()<id)i++;
00210   if(i<fifos.size() && fifos[i]->getId()==id)return fifos[i];
00211   else if(i>=fifos.size()){
00212     fifo=new FIFO(id);
00213     fifos.push_back(fifo);
00214   }else{
00215     fifo=new FIFO(id);
00216     fifos.push_back(NULL);
00217     for(int j=fifos.size()-1;j>i;j--)fifos[j]=fifos[j-1];
00218     fifos[i]=fifo;
00219   }
00220   return fifo;
00221 }
00222 
00223 /*invoked when parsing sdfgconf.txt. When reading a line starting with I, invoke this method to create a new INode; refer
00224   to the document regarding what each element in params array means*/
00225 void SDFG::getINode(int nodeId, int params[], int count){
00226   gin = new INode(nodeId,NULL);
00227   addNode(gin);
00228   for(int i=0;i<count;i++){
00229     FIFO *fifo=getFIFO(params[i]);
00230     gin->addOutbound(fifo);
00231     fifo->setSrc(gin);
00232   }
00233 }
00234 
00235 /*invoked when parsing sdfgconf.txt. When reading a line starting with O, invoke this method to create a new ONode; refer
00236   to the document regarding what each element in params array means*/
00237 void SDFG::getONode(int nodeId, int params[], int count){
00238   gout = new ONode(nodeId,NULL);
00239   addNode(gout);
00240   for(int i=0;i<count;i++){
00241     FIFO *fifo=getFIFO(params[i]);
00242     gout->setInbound(fifo);
00243     fifo->setDst(gout);
00244   }
00245 }
00246 
00247 /*invoked when parsing sdfgconf.txt. When reading a line starting with A, invoke this method to create a new ANode; refer
00248   to the document regarding what each element in params array means*/
00249 void SDFG::getANode(int nodeId, int params[], int count){
00250   ANode *anode = new ANode(nodeId);
00251   addNode(anode);
00252   FIFO *in1=NULL, *in2=NULL;
00253   for(int i=0; i<count; i++){
00254     if(i==0){
00255       in1 = getFIFO(params[i]);
00256       in1->setDst(anode);
00257     }else if(i==1){
00258       in2 = getFIFO(params[i]);
00259       in2->setDst(anode);
00260       anode->setInbound(in1, in2);
00261     }else{
00262       FIFO *out = getFIFO(params[i]);
00263       out->setSrc(anode);
00264       anode->addOutbound(out);
00265     }
00266   }
00267 }
00268 
00269 
00270 /*invoked when parsing sdfgconf.txt. When reading a line starting with S, invoke this method to create a new SNode; refer
00271   to the document regarding what each element in params array means*/
00272 void SDFG::getSNode(int nodeId, int params[], int count){
00273   SNode *snode = new SNode(nodeId);
00274   addNode(snode);
00275   FIFO *in1=NULL, *in2=NULL;
00276   for(int i=0; i<count; i++){
00277     if(i==0){
00278       in1=getFIFO(params[i]);
00279       in1->setDst(snode);
00280     }else if(i==1){
00281       in2=getFIFO(params[i]);
00282       in2->setDst(snode);
00283       snode->setInbound(in1,in2);
00284     }else{
00285       FIFO *out = getFIFO(params[i]);
00286       out->setSrc(snode);
00287       snode->addOutbound(out);
00288     }
00289   }
00290 }
00291 
00292 /*invoked when parsing sdfgconf.txt. When reading a line starting with M, invoke this method to create a new MNode; refer
00293   to the document regarding what each element in params array means*/
00294 void SDFG::getMNode(int nodeId, int params[], int count){
00295   MNode *mnode = new MNode(nodeId, params[0], params[1]);
00296   addNode(mnode);
00297   for(int i=2; i<count; i++){
00298     if(i==2){
00299       FIFO *in=getFIFO(params[i]);
00300       in->setDst(mnode);
00301       mnode->setInbound(in);
00302     }else{
00303       FIFO *out=getFIFO(params[i]);
00304       out->setSrc(mnode);
00305       mnode->addOutbound(out);
00306     }
00307   }
00308 }
00309 
00310 /*invoked when parsing sdfgconf.txt. When reading a line starting with D, invoke this method to create a new DNode; refer
00311   to the document regarding what each element in params array means*/
00312 void SDFG::getDNode(int nodeId, int params[], int count){
00313   DNode *dnode=new DNode(nodeId, params[0]);
00314   addNode(dnode);
00315   for(int i=1; i<count; i++){
00316     if(i==1){
00317       FIFO *in=getFIFO(params[i]);
00318       in->setDst(dnode);
00319       dnode->setInbound(in);
00320     }else{
00321       FIFO *out=getFIFO(params[i]);
00322       out->setSrc(dnode);
00323       dnode->addOutbound(out);
00324     }
00325   }
00326 }
00327 
00328 /*invoked when parsing sdfgconf.txt. When reading a line starting with U, invoke this method to create a new UNode; refer
00329   to the document regarding what each element in params array means*/
00330 void SDFG::getUNode(int nodeId, int params[], int count){
00331   UNode *unode = new UNode(nodeId, params[0]);
00332   addNode(unode);
00333   for(int i=1; i<count; i++){
00334     if(i==1){
00335       FIFO *in=getFIFO(params[i]);
00336       in->setDst(unode);
00337       unode->setInbound(in);
00338     }else{
00339       FIFO *out=getFIFO(params[i]);
00340       out->setSrc(unode);
00341       unode->addOutbound(out);
00342     }
00343   }
00344 }
00345 
00346 /*invoked when parsing sdfgconf.txt. When reading a line starting with C, invoke this method to create a new CNode; refer
00347   to the document regarding what each element in params array means*/
00348 void SDFG::getCNode(int nodeId, int params[], int count){
00349   CNode *cnode=new CNode(nodeId, params[0]);
00350   addNode(cnode);
00351   for(int i=1; i<count; i++){
00352     FIFO *out=getFIFO(params[i]);
00353     out->setSrc(cnode);
00354     cnode->addOutbound(out);
00355   }
00356 }
00357 
00358 /*invoked when parsing sdfgconf.txt. When reading a line starting with F, invoke this method to create a new FNode; refer
00359   to the document regarding what each element in params array means*/
00360 void SDFG::getFNode(int nodeId, int params[], int count){
00361   FNode *fnode=new FNode(nodeId);
00362   addNode(fnode);
00363   for(int i=0; i<count; i++){
00364     if(i==0){
00365       FIFO *in=getFIFO(params[i]);
00366       in->setDst(fnode);
00367       fnode->setInbound(in);
00368     }else{
00369       FIFO *out=getFIFO(params[i]);
00370       out->setSrc(fnode);
00371       fnode->addOutbound(out);
00372     }
00373   }
00374 }
00375 
00376 /*invoked when parsing sdfgconf.txt. When reading a line starting with E, invoke this method to add delay to a specific edge,
00377   namely put initial data into the FIFO associated with the edge; refer to the document regarding what each element in params array means*/
00378 void SDFG::addDelay(int params[], int count){
00379   FIFO *fifo=getFIFOAt(params[0]);
00380   if(!fifo){
00381     error("trying to add delay to a nonexisting edge\r\n");
00382     exit(1);
00383   }
00384   for(int i=0; i<params[1]; i++){
00385     fifo->putData(params[i+2]);
00386   }
00387 }
00388 
00389 /*Each row in topology matrix corresponds to a FIFO; on a row-by-row basis, if node is the producer (src) of a FIFO, then set
00390   tokenProduced to be the number of tokens the producer produces; the same for consumer; the number of tokens produced or consumed
00391   can be found in the specification*/
00392 void SDFG::buildTopologyMatrix(){
00393   SDFNode *src=NULL, *dst=NULL;
00394   int tokenProduced=0, tokenConsumed=0;
00395   for(int i=0; i<fifos.size(); i++){
00396     tokenConsumed=tokenProduced=1;
00397     src=fifos[i]->getSrc();
00398     dst=fifos[i]->getDst();
00399     if(src->getType()==U){
00400       UNode *unode=(UNode*) src;
00401       tokenProduced=unode->getNumOfCopies();
00402     }
00403     if(dst->getType()==D){
00404       DNode *dnode=(DNode*) dst;
00405       tokenConsumed=dnode->getNumOfSamples();
00406     }
00407     topologyMatrix[i].setValue(src->getId(), tokenProduced, dst->getId(), tokenConsumed);
00408   }
00409 }
00410 
00411 /*print the full topology matrix*/
00412 void SDFG::printTopologyMatrix()const{
00413   for(int i=0; i<fifos.size(); i++){
00414     for(int j=0; j<nodes.size(); j++){
00415       if(topologyMatrix[i].getSrc()==nodes[j]->getId())printf("%d ", topologyMatrix[i].getTokensProduced());
00416       else if(topologyMatrix[i].getDst()==nodes[j]->getId())printf("%d ", 0-topologyMatrix[i].getTokensConsumed());
00417       else printf("0 ");
00418     }
00419     printf("\r\n");
00420   }
00421 }
00422 
00423 /*test if the SDF has a schedule by solving the equation group; RationalNum is a class used to represent rational numbers,
00424   useful in producing integer solutions to equation groups*/
00425 bool SDFG::hasSchedule(){
00426   /*if this function has been called before, just return the recorded result*/
00427   if(scheduleTested)return schedulable;
00428   /*solution to the equation group, at most 256 variables, each variable corresponds to a node in SDF*/
00429   vector<RationalNum> solution(256);
00430   /*count keeps track of the number of variables in the equation group whose value has been found*/
00431   int count=0;
00432   /*initial values for the variables, initialize them to be -1 to flag that their values have not been found*/
00433   for(int i=0; i<256; i++)solution[i]=RationalNum(-1);
00434   /*set the value of first variable to 1, this is OK since the solution to the equation group is not unique*/
00435   solution[0]=RationalNum(1);
00436   count++;
00437   /*repeat for each equation until the values of all variables have been found*/
00438   do{
00439     for(int i=0; i<numOfFIFOs; i++){
00440       /*node1 and node2 correspond to the src and dst of the FIFO, we use them to index into the solution vector*/
00441       int node1,node2;
00442       node1=topologyMatrix[i].getSrc();
00443       node2=topologyMatrix[i].getDst();
00444       /*we have found the values for neither of them, there is nothing more we can do for now, so just skip and proceed*/
00445       if(solution[node1]<0&&solution[node2]<0)continue;
00446       /*we have found the values for both of them, then we plug in their values into this equation to see if the solution
00447         satisfies this equation*/
00448       else if(solution[node1]>=0&&solution[node2]>=0){
00449         /*values which we already found do not satisfy this current equation, meaning there is conflict, namely there is no
00450           schedule for this SDF*/
00451         if(solution[node1]*topologyMatrix[i].getTokensProduced()!=solution[node2]*topologyMatrix[i].getTokensConsumed()){
00452           scheduleTested=true;
00453           schedulable=false;
00454           return false;
00455         }
00456       }
00457       /*node1's value is not found, but node2's value is found, then use node2 to solve node1*/
00458       else if(solution[node1]<0 && solution[node2]>=0){
00459         RationalNum r(topologyMatrix[i].getTokensConsumed(), topologyMatrix[i].getTokensProduced());
00460         solution[node1]=r*solution[node2];
00461         /*we have found the value for one more variable, thus we should update count*/
00462         count++;
00463       }
00464       /*node2's value is not found, but node1's value is found, then use node1 to solve node2*/
00465       else if(solution[node1]>=0 && solution[node2]<0){
00466         RationalNum r(topologyMatrix[i].getTokensProduced(), topologyMatrix[i].getTokensConsumed());
00467         solution[node2]=r*solution[node1];
00468         /*we have found the value for one more variable, thus we should update count*/
00469         count++;
00470       }
00471     }
00472   }while(count<numOfNodes);
00473   /*adding all the elements in solution vector together; perform this process simply to make their denominators the same*/
00474   RationalNum temp(0);
00475   for(int i=0; i<numOfNodes; i++)temp=temp+solution[i];
00476   /*for each element in solution, multiply by the common denominator found just now; in this way, we can acquire a set of integer
00477     solution to the original equations group, this solution represents how many times a node has to run in a schedule, if there
00478     exists one; then store the values in numOfFiringRequired vector*/
00479   for(int i=0; i<numOfNodes; i++){
00480     solution[i]=solution[i]*temp.getDenominator();
00481     numOfFiringRequired.push_back(solution[i].getNumerator());
00482   }
00483   /*if we are here, we have found a schedule*/
00484   scheduleTested=true;
00485   schedulable=true;
00486   return true;
00487 }
00488 
00489 /*print number of times each node is required to fire in one schedule*/
00490 void SDFG::printNumOfFiringRequired()const{
00491   for(int i=0; i<numOfFiringRequired.size(); i++){
00492     printf("node %d will fire %d time(s)\r\n", i, numOfFiringRequired[i]);
00493   }
00494 }
00495 
00496 /*compile a schedule according to numOfFiringRequired; each time find a node which can fire and fire it; update the tokens on each FIFO,
00497   repeat this process until all the nodes have fired the required number of times, which means a complete schedule has finished*/
00498 void SDFG::makeSchedule(){
00499   vector<int> buffers(fifos.size()), firingCount(nodes.size());
00500   for(int i=0; i<buffers.size(); i++)buffers[i]=fifos[i]->getSize();
00501   for(int i=0; i<firingCount.size(); i++)firingCount[i]=0;
00502   bool finished;
00503   do{
00504       /*check if all nodes have fired the number of times required, as computed in hasSchedule() function*/
00505       finished=true;
00506       for(int i=0; i<firingCount.size(); i++){
00507         if(firingCount[i]<numOfFiringRequired[i]){
00508           /*this node has not fired that many times, then it has not finished*/
00509           finished=false;
00510           vector<int> tempBuf(buffers);
00511           bool valid=true;
00512           /*test if this node can fire, namely if it has all its input data ready on the inbound FIFOs; we are doing matrix multiplication
00513             with a vector in a compressed form, if the resulting buffer only has non-negative elements, then it means this node can
00514             fire*/
00515           for(int j=0; j<tempBuf.size(); j++){
00516             if(topologyMatrix[j].getSrc()==i){
00517               tempBuf[j]+=topologyMatrix[j].getTokensProduced();
00518             }else if(topologyMatrix[j].getDst()==i){
00519               tempBuf[j]-=topologyMatrix[j].getTokensConsumed();
00520               if(tempBuf[j]<0){
00521                 valid=false;
00522                 break;
00523               }
00524             }
00525           }
00526           if(valid){
00527             /*fire this node*/
00528             firingCount[i]++;
00529             schedule.push_back(i);
00530             for(int j=0; j<tempBuf.size(); j++)buffers[j]=tempBuf[j];
00531           }
00532         }
00533       }
00534   }while(!finished);
00535 }
00536 
00537 /*display schedule*/
00538 void SDFG::printSchedule()const{
00539   for(int i=0; i<schedule.size(); i++){
00540     printf("fire node %d ", schedule[i]);
00541     nodes[schedule[i]]->display();
00542   }
00543 }
00544 
00545 /*set the input of the SDF to a ring buffer buf*/
00546 void SDFG::setInput(RingBuffer *buf){
00547   gin->setInput(buf);
00548 }
00549 
00550 /*set the output of the SDF to a ring buffer buf*/
00551 void SDFG::setOutput(RingBuffer *buf){
00552   gout->setOutput(buf);
00553 }
00554 
00555 /*execute the SDF according to the computed schedule, firing each node for required number of times, repeat this process for
00556   numOfRepetitions iterations*/
00557 void SDFG::execute(int numOfRepetitions){
00558   for(int i=0; i<numOfRepetitions; i++){
00559     for(int j=0; j<schedule.size(); j++){
00560       getNodeAt(schedule[j])->execute();
00561     }
00562   }
00563 }