Diff: SDF.cpp

Revision:

0:1c8f2727e9f5

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/SDF.cpp	Thu Apr 03 22:56:32 2014 +0000
@@ -0,0 +1,563 @@
+#include "SDF.h"
+
+/*set the input to a ring buffer pointed to by buf, the input node will read input from this ring buffer*/
+void INode::setInput(RingBuffer *buf){
+  input=buf;
+}
+
+/*each time inode executes, reading one sample from input ring buffer, and put this data onto all the outgoing edges*/
+void INode::execute(){
+  int inputSample = input->next();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    outbounds[i]->putData(inputSample);
+  }
+}
+
+/*display function*/
+void INode::display()const{
+  printf("INode id=%d type=%d ", id, type);
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*set the output to a ring buffer pointed to by buf, the output node will write output samples into this buf*/
+void ONode::setOutput(RingBuffer *buf){
+  output=buf;
+}
+
+/*each time onode executes, reading one sample from inbound FIFO and write this sample to ring buffer; also compute checksum*/
+void ONode::execute(){
+  int sampleOut=inbound->getData();
+  checksum ^= sampleOut;
+  output->insert(sampleOut);
+}
+
+/*display function*/
+void ONode::display()const{
+  printf("ONode id=%d type=%d %d\r\n", id, type, inbound->getId());
+}
+
+/*each time anode executes, reading operand1 from one inbound FIFO op1, reading operand2 from the other inbound FIFO op2,
+ compute the sum of the two and put this result onto all the outbound FIFOs*/
+void ANode::execute(){
+  int a = op1->getData(), b = op2->getData();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    outbounds[i]->putData(a+b);
+  }
+}
+
+/*display function*/
+void ANode::display()const{
+  printf("ANode id=%d type=%d %d %d ", id, type, op1->getId(), op2->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time anode executes, reading operand1 from one inbound FIFO op1, reading operand2 from the other inbound FIFO op2,
+ compute the difference of the two and put this result onto all the outbound FIFOs*/
+void SNode::execute(){
+  int a = op1->getData(), b = op2->getData();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    outbounds[i]->putData(a-b);
+  }
+}
+
+/*display function*/
+void SNode::display()const{
+  printf("SNode id=%d type=%d %d %d ", id, type, op1->getId(), op2->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time mnode executes, reading a sample from inbound FIFO, multiply it by c and divide by d, put the result onto all
+ the outbound FIFOs*/
+void MNode::execute(){
+  int a = inbound->getData();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    outbounds[i]->putData(a*c/d);
+  }
+}
+
+/*display function*/
+void MNode::display()const{
+  printf("MNode id=%d type=%d c=%d d=%d %d ", id, type, c, d, inbound->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time dnode executes, read numOfSamples samples from inbound FIFO, put the first sample (sample 0) onto all the outbound FIFOs*/
+void DNode::execute(){
+  for(int i=0; i<numOfSamples; i++){
+    int d = inbound->getData();
+    if(i==0){
+      for(int j=0; j<(int)outbounds.size(); j++)outbounds[j]->putData(d);
+    }
+  }
+}
+
+/*display function*/
+void DNode::display()const{
+  printf("DNode id=%d type=%d n=%d %d ", id, type, numOfSamples, inbound->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time unode executes, read a sample from inbound FIFO, duplicate numOfCopies copies, put all those copies onto outbound FIFOs*/
+void UNode::execute(){
+  int a = inbound->getData();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    for(int j=0; j<numOfCopies; j++){outbounds[i]->putData(a);}
+  }
+}
+
+/*display function*/
+void UNode::display()const{
+  printf("UNode id=%d type=%d n=%d %d ", id, type, numOfCopies, inbound->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time cnode executes, put the constant onto outbound FIFOs*/
+void CNode::execute(){
+  for(int i=0; i<outbounds.size(); i++){
+    outbounds[i]->putData(constant);
+  }
+}
+
+/*display function*/
+void CNode::display()const{
+  printf("CNode id=%d type=%d constant=%d ", id, type, constant);
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*each time fnode executes, read a sample from inbound FIFO, and put this sample onto outbound FIFOs*/
+void FNode::execute(){
+  int a = inbound->getData();
+  for(int i=0; i<(int)outbounds.size(); i++){
+    outbounds[i]->putData(a);
+  }
+}
+
+/*display function*/
+void FNode::display()const{
+  printf("FNode id=%d type=%d %d ", id, type, inbound->getId());
+  for(int i=0; i<outbounds.size(); i++)printf("%d ", outbounds[i]->getId());
+  printf("\r\n");
+}
+
+/*intended for the consumer to use, read one sample from the FIFO, and remove that data*/
+int FIFO::getData(){
+  if(this->fifo.empty()){
+    error("trying to read from empty FIFO: id=%d...\r\n", this->id);
+    exit(1);
+  }
+  int ret = this->fifo.front();
+  this->fifo.pop();
+  return ret;
+}
+
+/*intended for the producer to use, put one sample into the FIFO*/
+void FIFO::putData(int d){
+  this->fifo.push(d);
+}
+
+/*display function*/
+void FIFO::display()const{
+  printf("FIFO id=%d src=%d dst=%d numOfMarkings=%d\r\n", id, src->getId(), dst->getId(), fifo.size());
+}
+
+SDFG::SDFG(char* path, RingBuffer* input, RingBuffer* output):
+   gin(NULL),gout(NULL),numOfNodes(0),numOfFIFOs(0),scheduleTested(false),schedulable(false), scheduleFound(false)
+{
+    Parser::parseSDFG(path,this);
+    if(!hasSchedule()){
+        error("ERROR: CANNOT SCHEDULE\r\n");
+        exit(1);
+    }
+    setInput(input);
+    setOutput(output);
+    makeSchedule();
+}
+
+/*destructor, reclaim all the space allocated for nodes and FIFOs*/
+SDFG::~SDFG(){
+  for(int i=0; i<nodes.size(); i++)delete nodes[i];
+  for(int i=0; i<fifos.size(); i++)delete fifos[i];
+}
+
+/*add a node into the nodes vector, keep the nodes whose id's are arranged in ascending order in the nodes vector;
+  basically an insertion-sort*/
+void SDFG::addNode(SDFNode *node){
+  if(!node)return;
+  int i=0;
+  while(i<nodes.size()&&nodes[i]->getId()<node->getId())i++;
+  if(i<nodes.size()&&nodes[i]->getId()==node->getId())return;
+  else if(i>=nodes.size())nodes.push_back(node);
+  else{
+    nodes.push_back(NULL);
+    for(int j=nodes.size()-1;j>i;j--)nodes[j]=nodes[j-1];
+    nodes[i]=node;
+  }
+}
+
+/*given an id, if a FIFO with that id exists, return that FIFO; otherwise create a new FIFO, insert the FIFO into
+  vector fifos, and return that FIFO; also an insertion-sort implementation*/
+FIFO* SDFG::getFIFO(int id){
+  int i=0;
+  FIFO *fifo=NULL;
+  while(i<fifos.size()&&fifos[i]->getId()<id)i++;
+  if(i<fifos.size() && fifos[i]->getId()==id)return fifos[i];
+  else if(i>=fifos.size()){
+    fifo=new FIFO(id);
+    fifos.push_back(fifo);
+  }else{
+    fifo=new FIFO(id);
+    fifos.push_back(NULL);
+    for(int j=fifos.size()-1;j>i;j--)fifos[j]=fifos[j-1];
+    fifos[i]=fifo;
+  }
+  return fifo;
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with I, invoke this method to create a new INode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getINode(int nodeId, int params[], int count){
+  gin = new INode(nodeId,NULL);
+  addNode(gin);
+  for(int i=0;i<count;i++){
+    FIFO *fifo=getFIFO(params[i]);
+    gin->addOutbound(fifo);
+    fifo->setSrc(gin);
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with O, invoke this method to create a new ONode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getONode(int nodeId, int params[], int count){
+  gout = new ONode(nodeId,NULL);
+  addNode(gout);
+  for(int i=0;i<count;i++){
+    FIFO *fifo=getFIFO(params[i]);
+    gout->setInbound(fifo);
+    fifo->setDst(gout);
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with A, invoke this method to create a new ANode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getANode(int nodeId, int params[], int count){
+  ANode *anode = new ANode(nodeId);
+  addNode(anode);
+  FIFO *in1=NULL, *in2=NULL;
+  for(int i=0; i<count; i++){
+    if(i==0){
+      in1 = getFIFO(params[i]);
+      in1->setDst(anode);
+    }else if(i==1){
+      in2 = getFIFO(params[i]);
+      in2->setDst(anode);
+      anode->setInbound(in1, in2);
+    }else{
+      FIFO *out = getFIFO(params[i]);
+      out->setSrc(anode);
+      anode->addOutbound(out);
+    }
+  }
+}
+
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with S, invoke this method to create a new SNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getSNode(int nodeId, int params[], int count){
+  SNode *snode = new SNode(nodeId);
+  addNode(snode);
+  FIFO *in1=NULL, *in2=NULL;
+  for(int i=0; i<count; i++){
+    if(i==0){
+      in1=getFIFO(params[i]);
+      in1->setDst(snode);
+    }else if(i==1){
+      in2=getFIFO(params[i]);
+      in2->setDst(snode);
+      snode->setInbound(in1,in2);
+    }else{
+      FIFO *out = getFIFO(params[i]);
+      out->setSrc(snode);
+      snode->addOutbound(out);
+    }
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with M, invoke this method to create a new MNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getMNode(int nodeId, int params[], int count){
+  MNode *mnode = new MNode(nodeId, params[0], params[1]);
+  addNode(mnode);
+  for(int i=2; i<count; i++){
+    if(i==2){
+      FIFO *in=getFIFO(params[i]);
+      in->setDst(mnode);
+      mnode->setInbound(in);
+    }else{
+      FIFO *out=getFIFO(params[i]);
+      out->setSrc(mnode);
+      mnode->addOutbound(out);
+    }
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with D, invoke this method to create a new DNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getDNode(int nodeId, int params[], int count){
+  DNode *dnode=new DNode(nodeId, params[0]);
+  addNode(dnode);
+  for(int i=1; i<count; i++){
+    if(i==1){
+      FIFO *in=getFIFO(params[i]);
+      in->setDst(dnode);
+      dnode->setInbound(in);
+    }else{
+      FIFO *out=getFIFO(params[i]);
+      out->setSrc(dnode);
+      dnode->addOutbound(out);
+    }
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with U, invoke this method to create a new UNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getUNode(int nodeId, int params[], int count){
+  UNode *unode = new UNode(nodeId, params[0]);
+  addNode(unode);
+  for(int i=1; i<count; i++){
+    if(i==1){
+      FIFO *in=getFIFO(params[i]);
+      in->setDst(unode);
+      unode->setInbound(in);
+    }else{
+      FIFO *out=getFIFO(params[i]);
+      out->setSrc(unode);
+      unode->addOutbound(out);
+    }
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with C, invoke this method to create a new CNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getCNode(int nodeId, int params[], int count){
+  CNode *cnode=new CNode(nodeId, params[0]);
+  addNode(cnode);
+  for(int i=1; i<count; i++){
+    FIFO *out=getFIFO(params[i]);
+    out->setSrc(cnode);
+    cnode->addOutbound(out);
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with F, invoke this method to create a new FNode; refer
+  to the document regarding what each element in params array means*/
+void SDFG::getFNode(int nodeId, int params[], int count){
+  FNode *fnode=new FNode(nodeId);
+  addNode(fnode);
+  for(int i=0; i<count; i++){
+    if(i==0){
+      FIFO *in=getFIFO(params[i]);
+      in->setDst(fnode);
+      fnode->setInbound(in);
+    }else{
+      FIFO *out=getFIFO(params[i]);
+      out->setSrc(fnode);
+      fnode->addOutbound(out);
+    }
+  }
+}
+
+/*invoked when parsing sdfgconf.txt. When reading a line starting with E, invoke this method to add delay to a specific edge,
+  namely put initial data into the FIFO associated with the edge; refer to the document regarding what each element in params array means*/
+void SDFG::addDelay(int params[], int count){
+  FIFO *fifo=getFIFOAt(params[0]);
+  if(!fifo){
+    error("trying to add delay to a nonexisting edge\r\n");
+    exit(1);
+  }
+  for(int i=0; i<params[1]; i++){
+    fifo->putData(params[i+2]);
+  }
+}
+
+/*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
+  tokenProduced to be the number of tokens the producer produces; the same for consumer; the number of tokens produced or consumed
+  can be found in the specification*/
+void SDFG::buildTopologyMatrix(){
+  SDFNode *src=NULL, *dst=NULL;
+  int tokenProduced=0, tokenConsumed=0;
+  for(int i=0; i<fifos.size(); i++){
+    tokenConsumed=tokenProduced=1;
+    src=fifos[i]->getSrc();
+    dst=fifos[i]->getDst();
+    if(src->getType()==U){
+      UNode *unode=(UNode*) src;
+      tokenProduced=unode->getNumOfCopies();
+    }
+    if(dst->getType()==D){
+      DNode *dnode=(DNode*) dst;
+      tokenConsumed=dnode->getNumOfSamples();
+    }
+    topologyMatrix[i].setValue(src->getId(), tokenProduced, dst->getId(), tokenConsumed);
+  }
+}
+
+/*print the full topology matrix*/
+void SDFG::printTopologyMatrix()const{
+  for(int i=0; i<fifos.size(); i++){
+    for(int j=0; j<nodes.size(); j++){
+      if(topologyMatrix[i].getSrc()==nodes[j]->getId())printf("%d ", topologyMatrix[i].getTokensProduced());
+      else if(topologyMatrix[i].getDst()==nodes[j]->getId())printf("%d ", 0-topologyMatrix[i].getTokensConsumed());
+      else printf("0 ");
+    }
+    printf("\r\n");
+  }
+}
+
+/*test if the SDF has a schedule by solving the equation group; RationalNum is a class used to represent rational numbers,
+  useful in producing integer solutions to equation groups*/
+bool SDFG::hasSchedule(){
+  /*if this function has been called before, just return the recorded result*/
+  if(scheduleTested)return schedulable;
+  /*solution to the equation group, at most 256 variables, each variable corresponds to a node in SDF*/
+  vector<RationalNum> solution(256);
+  /*count keeps track of the number of variables in the equation group whose value has been found*/
+  int count=0;
+  /*initial values for the variables, initialize them to be -1 to flag that their values have not been found*/
+  for(int i=0; i<256; i++)solution[i]=RationalNum(-1);
+  /*set the value of first variable to 1, this is OK since the solution to the equation group is not unique*/
+  solution[0]=RationalNum(1);
+  count++;
+  /*repeat for each equation until the values of all variables have been found*/
+  do{
+    for(int i=0; i<numOfFIFOs; i++){
+      /*node1 and node2 correspond to the src and dst of the FIFO, we use them to index into the solution vector*/
+      int node1,node2;
+      node1=topologyMatrix[i].getSrc();
+      node2=topologyMatrix[i].getDst();
+      /*we have found the values for neither of them, there is nothing more we can do for now, so just skip and proceed*/
+      if(solution[node1]<0&&solution[node2]<0)continue;
+      /*we have found the values for both of them, then we plug in their values into this equation to see if the solution
+        satisfies this equation*/
+      else if(solution[node1]>=0&&solution[node2]>=0){
+        /*values which we already found do not satisfy this current equation, meaning there is conflict, namely there is no
+          schedule for this SDF*/
+        if(solution[node1]*topologyMatrix[i].getTokensProduced()!=solution[node2]*topologyMatrix[i].getTokensConsumed()){
+          scheduleTested=true;
+          schedulable=false;
+          return false;
+        }
+      }
+      /*node1's value is not found, but node2's value is found, then use node2 to solve node1*/
+      else if(solution[node1]<0 && solution[node2]>=0){
+        RationalNum r(topologyMatrix[i].getTokensConsumed(), topologyMatrix[i].getTokensProduced());
+        solution[node1]=r*solution[node2];
+        /*we have found the value for one more variable, thus we should update count*/
+        count++;
+      }
+      /*node2's value is not found, but node1's value is found, then use node1 to solve node2*/
+      else if(solution[node1]>=0 && solution[node2]<0){
+        RationalNum r(topologyMatrix[i].getTokensProduced(), topologyMatrix[i].getTokensConsumed());
+        solution[node2]=r*solution[node1];
+        /*we have found the value for one more variable, thus we should update count*/
+        count++;
+      }
+    }
+  }while(count<numOfNodes);
+  /*adding all the elements in solution vector together; perform this process simply to make their denominators the same*/
+  RationalNum temp(0);
+  for(int i=0; i<numOfNodes; i++)temp=temp+solution[i];
+  /*for each element in solution, multiply by the common denominator found just now; in this way, we can acquire a set of integer
+    solution to the original equations group, this solution represents how many times a node has to run in a schedule, if there
+    exists one; then store the values in numOfFiringRequired vector*/
+  for(int i=0; i<numOfNodes; i++){
+    solution[i]=solution[i]*temp.getDenominator();
+    numOfFiringRequired.push_back(solution[i].getNumerator());
+  }
+  /*if we are here, we have found a schedule*/
+  scheduleTested=true;
+  schedulable=true;
+  return true;
+}
+
+/*print number of times each node is required to fire in one schedule*/
+void SDFG::printNumOfFiringRequired()const{
+  for(int i=0; i<numOfFiringRequired.size(); i++){
+    printf("node %d will fire %d time(s)\r\n", i, numOfFiringRequired[i]);
+  }
+}
+
+/*compile a schedule according to numOfFiringRequired; each time find a node which can fire and fire it; update the tokens on each FIFO,
+  repeat this process until all the nodes have fired the required number of times, which means a complete schedule has finished*/
+void SDFG::makeSchedule(){
+  vector<int> buffers(fifos.size()), firingCount(nodes.size());
+  for(int i=0; i<buffers.size(); i++)buffers[i]=fifos[i]->getSize();
+  for(int i=0; i<firingCount.size(); i++)firingCount[i]=0;
+  bool finished;
+  do{
+      /*check if all nodes have fired the number of times required, as computed in hasSchedule() function*/
+      finished=true;
+      for(int i=0; i<firingCount.size(); i++){
+        if(firingCount[i]<numOfFiringRequired[i]){
+          /*this node has not fired that many times, then it has not finished*/
+          finished=false;
+          vector<int> tempBuf(buffers);
+          bool valid=true;
+          /*test if this node can fire, namely if it has all its input data ready on the inbound FIFOs; we are doing matrix multiplication
+            with a vector in a compressed form, if the resulting buffer only has non-negative elements, then it means this node can
+            fire*/
+          for(int j=0; j<tempBuf.size(); j++){
+            if(topologyMatrix[j].getSrc()==i){
+              tempBuf[j]+=topologyMatrix[j].getTokensProduced();
+            }else if(topologyMatrix[j].getDst()==i){
+              tempBuf[j]-=topologyMatrix[j].getTokensConsumed();
+              if(tempBuf[j]<0){
+                valid=false;
+                break;
+              }
+            }
+          }
+          if(valid){
+            /*fire this node*/
+            firingCount[i]++;
+            schedule.push_back(i);
+            for(int j=0; j<tempBuf.size(); j++)buffers[j]=tempBuf[j];
+          }
+        }
+      }
+  }while(!finished);
+}
+
+/*display schedule*/
+void SDFG::printSchedule()const{
+  for(int i=0; i<schedule.size(); i++){
+    printf("fire node %d ", schedule[i]);
+    nodes[schedule[i]]->display();
+  }
+}
+
+/*set the input of the SDF to a ring buffer buf*/
+void SDFG::setInput(RingBuffer *buf){
+  gin->setInput(buf);
+}
+
+/*set the output of the SDF to a ring buffer buf*/
+void SDFG::setOutput(RingBuffer *buf){
+  gout->setOutput(buf);
+}
+
+/*execute the SDF according to the computed schedule, firing each node for required number of times, repeat this process for
+  numOfRepetitions iterations*/
+void SDFG::execute(int numOfRepetitions){
+  for(int i=0; i<numOfRepetitions; i++){
+    for(int j=0; j<schedule.size(); j++){
+      getNodeAt(schedule[j])->execute();
+    }
+  }
+}
\ No newline at end of file