SDF.h

00001 #ifndef _SDF_H
00002 #define _SDF_H
00003 
00004 #include "mbed.h"
00005 #include "RationalNum.h"
00006 #include "RingBuffer.h"
00007 #include "Parser.h"
00008 #include <queue>
00009 #include <vector>
00010 
00011 
00012 using namespace std;
00013 
00014 enum NodeType {I, O, A, S, M, D, U, C, F};
00015 
00016 class FIFO;
00017 
00018 /*base class for all kinds of node in SDF*/
00019 class SDFNode{
00020 protected:
00021   int id;
00022   NodeType type;
00023 public:
00024   virtual int getId()const=0;
00025   virtual NodeType getType()const=0;
00026   virtual void execute()=0;
00027   virtual void display()const=0;
00028 };
00029 
00030 /*input node*/
00031 class INode : public SDFNode{
00032 private:
00033   /*input data, inode reads data from a ring buffer*/
00034   RingBuffer *input;
00035   /*edges (fifos) going outward from this node*/
00036   vector<FIFO*> outbounds;
00037 public:
00038   INode(int k=-1,RingBuffer *in=NULL){id=k;input=in;type=I;}
00039   ~INode(){input=NULL;}
00040   virtual int getId()const{return id;}
00041   virtual NodeType getType()const{return type;}
00042   virtual void execute();
00043   virtual void display()const;
00044   void setInput(RingBuffer *buf);
00045   void addOutbound(FIFO* fifo){outbounds.push_back(fifo);}
00046 };
00047 
00048 /*output node*/
00049 class ONode : public SDFNode{
00050 private:
00051   /*edge coming into this node*/
00052   FIFO *inbound;
00053   /*ring buffer where to write output*/
00054   RingBuffer *output;
00055   /*checksum of all output samples*/
00056   int checksum;
00057 public:
00058   ONode(int k=-1,RingBuffer *out=NULL):checksum(0){id=k;output=out;type=O;}
00059   ~ONode(){inbound=NULL;output=NULL;}
00060   virtual int getId()const{return id;}
00061   virtual NodeType getType()const{return type;}
00062   virtual void execute();
00063   virtual void display()const;
00064   virtual void setInbound(FIFO* fifo){inbound=fifo;}
00065   void setOutput(RingBuffer *buf);
00066   int getChecksum()const{return checksum;}
00067 };
00068 
00069 class ANode : public SDFNode{
00070 private:
00071   /*two edges coming into this node, representing the two operands in an addition: op1+op2*/
00072   FIFO *op1, *op2;
00073   /*edges going outward from this node*/
00074   vector<FIFO*> outbounds;
00075 public:
00076   ANode(int k=-1){id=k;type=A;}
00077   ~ANode(){op1=op2=NULL;}
00078   virtual int getId()const{return id;}
00079   virtual NodeType getType()const{return type;}
00080   virtual void execute();
00081   virtual void display()const;
00082   void addOutbound(FIFO* fifo){outbounds.push_back(fifo);}
00083   void setInbound(FIFO *in1, FIFO *in2){op1=in1;op2=in2;}
00084 };
00085 
00086 class SNode : public SDFNode{
00087 private:
00088   /*two edges coming into this node, representing the two operands in an subtraction: op1-op2*/
00089   FIFO *op1, *op2;
00090   /*edges going outward from this node*/
00091   vector<FIFO*> outbounds;
00092 public:
00093   SNode(int k=-1){id=k;type=S;}
00094   ~SNode(){op1=op2=NULL;}
00095   virtual int getId()const{return id;}
00096   virtual NodeType getType()const{return type;}
00097   virtual void execute();
00098   virtual void display()const;
00099   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00100   void setInbound(FIFO *in1, FIFO *in2){op1=in1; op2=in2;}
00101 };
00102 
00103 class MNode : public SDFNode{
00104 private:
00105   /*edge providing input data for this node*/
00106   FIFO *inbound;
00107   /*coefficients needed by the multiplier: as specified in the document, op*c/d */
00108   int c,d;
00109   /*edges going outward from this node*/
00110   vector<FIFO*> outbounds;
00111 public:
00112   MNode(int k=-1, int i=1, int j=1){id=k;c=i;d=j;type=M;}
00113   ~MNode(){inbound=NULL;}
00114   virtual int getId()const{return id;}
00115   virtual NodeType getType()const{return type;}
00116   virtual void execute();
00117   virtual void display()const;
00118   void setInbound(FIFO *fifo){inbound=fifo;}
00119   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00120 };
00121 
00122 class DNode : public SDFNode{
00123 private:
00124   /*number of samples to read at a time from input edge*/
00125   int numOfSamples;
00126   /*edge providing input to this node*/
00127   FIFO *inbound;
00128   /*edges going outward from this node*/
00129   vector<FIFO*> outbounds;
00130 public:
00131   DNode(int k=-1, int n=0){id=k;numOfSamples=n;type=D;}
00132   ~DNode(){inbound=NULL;}
00133   virtual int getId()const{return id;}
00134   virtual NodeType getType()const{return type;}
00135   int getNumOfSamples()const{return numOfSamples;}
00136   virtual void execute();
00137   virtual void display()const;
00138   void setInbound(FIFO *fifo){inbound=fifo;}
00139   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00140 };
00141 
00142 class UNode : public SDFNode{
00143 private:
00144   /*number of samples to duplicate*/
00145   int numOfCopies;
00146   /*edge providing input to this node*/
00147   FIFO *inbound;
00148   /*edges going outward from this node*/
00149   vector<FIFO*> outbounds;
00150 public:
00151   UNode(int k=-1, int n=0){id=k;numOfCopies=n;type=U;}
00152   ~UNode(){inbound=NULL;}
00153   virtual int getId()const{return id;}
00154   virtual NodeType getType()const{return type;}
00155   int getNumOfCopies()const{return numOfCopies;}
00156   virtual void execute();
00157   virtual void display()const;
00158   void setInbound(FIFO *fifo){inbound=fifo;}
00159   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00160 };
00161 
00162 class CNode : public SDFNode{
00163 private:
00164   /*constant value this node provides*/
00165   const int constant;
00166   /*edges going outward from this node*/
00167   vector<FIFO*> outbounds;
00168 public:
00169   CNode(int k=-1, int c=0):constant(c){id=k;}
00170   ~CNode(){}
00171   virtual int getId()const{return id;}
00172   virtual NodeType getType()const{return type;}
00173   virtual void execute();
00174   virtual void display()const;
00175   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00176 };
00177 
00178 class FNode : public SDFNode{
00179 private:
00180   /*edge providing input to this node*/
00181   FIFO *inbound;
00182   /*edges going outward from this node*/
00183   vector<FIFO*> outbounds;
00184 public:
00185   FNode(int k=-1){id=k;type=F;}
00186   ~FNode(){inbound=NULL;}
00187   virtual int getId()const{return id;}
00188   virtual NodeType getType()const{return type;}
00189   virtual void execute();
00190   virtual void display()const;
00191   void setInbound(FIFO *fifo){inbound=fifo;}
00192   void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
00193 };
00194 
00195 /*each edge is represented by a First-in-First-out queue, producer puts data into the queue, consumer removes data from the queue*/
00196 class FIFO{
00197 private:
00198   /*id of the fifo*/
00199   int id;
00200   /*queue holding data*/
00201   queue<int> fifo;
00202   /*src is producer node, dst is consumer node*/
00203   SDFNode *src, *dst;
00204 public:
00205   int getData();
00206   void putData(int d);
00207   SDFNode *getSrc()const{return src;}
00208   SDFNode *getDst()const{return dst;}
00209   void setSrc(SDFNode *s){src=s;}
00210   void setDst(SDFNode *d){dst=d;}
00211   void display()const;
00212   int getId()const{return id;}
00213   int getSize()const{return fifo.size();}
00214   FIFO(int k=-1):id(k),src(NULL),dst(NULL){}
00215   ~FIFO(){src=dst=NULL;}
00216 };
00217 
00218 /*compressed topology matrix*/
00219 class TMatrixRow{
00220 private:
00221   /*srcNode is the id of the producer node, dstNode is the id of the consumer node*/
00222   int srcNode, dstNode;
00223   /*tokensProduced is the number of tokens produced by producer, tokensConsumed is the number of tokens consumed by consumer*/
00224   int tokensProduced, tokensConsumed;
00225 public:
00226   TMatrixRow(int sn=-1, int pt=-1, int dn=-1, int ct=-1):srcNode(sn),dstNode(dn),tokensProduced(pt),tokensConsumed(ct){}
00227   void setValue(int sn, int pt, int dn, int ct){srcNode=sn;tokensProduced=pt;dstNode=dn;tokensConsumed=ct;}
00228   int getSrc()const{return srcNode;}
00229   int getDst()const{return dstNode;}
00230   int getTokensConsumed()const{return tokensConsumed;}
00231   int getTokensProduced()const{return tokensProduced;}
00232 };
00233 
00234 /*synchronous data flow*/
00235 class SDFG{
00236 private:
00237   /*input node, each sdf has one and only one input node*/
00238   INode *gin;
00239   /*output node, each sdf has one and only one output node*/
00240   ONode *gout;
00241   /*list of nodes (including gin and gout)*/
00242   vector<SDFNode*> nodes;
00243   /*list of FIFOs*/
00244   vector<FIFO*> fifos;
00245   /*topology matrix corresponding to this sdf*/
00246   TMatrixRow topologyMatrix[256];
00247   /*number of nodes in sdf, equals nodes.size()*/
00248   int numOfNodes;
00249   /*number of FIFOs in sdf, equals fifos.size()*/
00250   int numOfFIFOs;
00251   /*if hasSchedule() method has ever been called, this variable is intended to avoid recalculating hasSchedule() again*/
00252   bool scheduleTested;
00253   /*mark if this sdf is schedulable; together with scheduleTested variable, we can avoid recalculating hasSchedule()*/
00254   bool schedulable;
00255   /*schedule, for example, 1,2,4,3... means firing node 1 first, then 2, then 4, then 3*/
00256   vector<int> schedule;
00257   /*a vector storing the number of times each node has to fire in ONE schedule, e.g. numOfFiringRequired[0] is the
00258     number of times node 0 has to fire in the schedule, numOfFiringRequired[1] is the number of times node 1 has to
00259     fire in the schedule*/
00260   vector<int> numOfFiringRequired;
00261   /*mark if a schedule has been found*/
00262   bool scheduleFound;
00263 public:
00264   SDFG():gin(NULL),gout(NULL),numOfNodes(0),numOfFIFOs(0),scheduleTested(false),schedulable(false), scheduleFound(false){}
00265   SDFG(char*, RingBuffer*, RingBuffer*);
00266   ~SDFG();
00267   INode *getInput()const{return this->gin;}
00268   ONode *getOutput()const{return this->gout;}
00269   void addNode(SDFNode *node);
00270   //get the fifo with a specific id, if the fifo does not exist, create one and insert into fifos.
00271   FIFO* getFIFO(int id);
00272   vector<SDFNode *> getNodes()const{return this->nodes;}
00273   SDFNode *getNodeAt(int i)const{return (i<this->nodes.size())? this->nodes[i]:NULL;}
00274   //get fifo at a position i in fifos vector, actually in our case, fifos is sorted vector indicating i is also the id of the fifo
00275   FIFO *getFIFOAt(int i)const{return (i<this->fifos.size()) ? this->fifos[i]:NULL;}
00276   vector<FIFO *> getFIFOs()const{return this->fifos;}
00277   int getNumOfNodes()const{return this->numOfNodes;}
00278   void setNumOfNodes(int k){numOfNodes=k;}
00279   int getNumOfFIFOs()const{return this->numOfFIFOs;}
00280   void setNumOfFIFOs(int k){numOfFIFOs=k;}
00281   //create node of specific kind
00282   void getINode(int nodeId, int params[], int count);
00283   void getONode(int nodeId, int params[], int count);
00284   void getANode(int nodeId, int params[], int count);
00285   void getSNode(int nodeId, int params[], int count);
00286   void getMNode(int nodeId, int params[], int count);
00287   void getDNode(int nodeId, int params[], int count);
00288   void getUNode(int nodeId, int params[], int count);
00289   void getCNode(int nodeId, int params[], int count);
00290   void getFNode(int nodeId, int params[], int count);
00291   void addDelay(int params[], int count);
00292   //build compressed topology matrix, compressing the columns
00293   void buildTopologyMatrix();
00294   void printTopologyMatrix()const;
00295   /*calling sequence: hasSchedule<makeSchedule<execute*/
00296   bool hasSchedule();
00297   vector<int> getNumOfFiringRequired()const{return numOfFiringRequired;}
00298   void printNumOfFiringRequired()const;
00299   void makeSchedule();
00300   void printSchedule()const;
00301   void setInput(RingBuffer *data);
00302   void setOutput(RingBuffer *buf);
00303   void execute(int numOfRepetions);
00304   int getChecksum()const{return gout->getChecksum();}
00305 };
00306 #endif