File content as of revision 0:1c8f2727e9f5:

#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();
    }
  }
}