Diff: SDF.h

Revision:

0:1c8f2727e9f5

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/SDF.h	Thu Apr 03 22:56:32 2014 +0000
@@ -0,0 +1,306 @@
+#ifndef _SDF_H
+#define _SDF_H
+
+#include "mbed.h"
+#include "RationalNum.h"
+#include "RingBuffer.h"
+#include "Parser.h"
+#include <queue>
+#include <vector>
+
+
+using namespace std;
+
+enum NodeType {I, O, A, S, M, D, U, C, F};
+
+class FIFO;
+
+/*base class for all kinds of node in SDF*/
+class SDFNode{
+protected:
+  int id;
+  NodeType type;
+public:
+  virtual int getId()const=0;
+  virtual NodeType getType()const=0;
+  virtual void execute()=0;
+  virtual void display()const=0;
+};
+
+/*input node*/
+class INode : public SDFNode{
+private:
+  /*input data, inode reads data from a ring buffer*/
+  RingBuffer *input;
+  /*edges (fifos) going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  INode(int k=-1,RingBuffer *in=NULL){id=k;input=in;type=I;}
+  ~INode(){input=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void setInput(RingBuffer *buf);
+  void addOutbound(FIFO* fifo){outbounds.push_back(fifo);}
+};
+
+/*output node*/
+class ONode : public SDFNode{
+private:
+  /*edge coming into this node*/
+  FIFO *inbound;
+  /*ring buffer where to write output*/
+  RingBuffer *output;
+  /*checksum of all output samples*/
+  int checksum;
+public:
+  ONode(int k=-1,RingBuffer *out=NULL):checksum(0){id=k;output=out;type=O;}
+  ~ONode(){inbound=NULL;output=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  virtual void setInbound(FIFO* fifo){inbound=fifo;}
+  void setOutput(RingBuffer *buf);
+  int getChecksum()const{return checksum;}
+};
+
+class ANode : public SDFNode{
+private:
+  /*two edges coming into this node, representing the two operands in an addition: op1+op2*/
+  FIFO *op1, *op2;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  ANode(int k=-1){id=k;type=A;}
+  ~ANode(){op1=op2=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void addOutbound(FIFO* fifo){outbounds.push_back(fifo);}
+  void setInbound(FIFO *in1, FIFO *in2){op1=in1;op2=in2;}
+};
+
+class SNode : public SDFNode{
+private:
+  /*two edges coming into this node, representing the two operands in an subtraction: op1-op2*/
+  FIFO *op1, *op2;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  SNode(int k=-1){id=k;type=S;}
+  ~SNode(){op1=op2=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+  void setInbound(FIFO *in1, FIFO *in2){op1=in1; op2=in2;}
+};
+
+class MNode : public SDFNode{
+private:
+  /*edge providing input data for this node*/
+  FIFO *inbound;
+  /*coefficients needed by the multiplier: as specified in the document, op*c/d */
+  int c,d;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  MNode(int k=-1, int i=1, int j=1){id=k;c=i;d=j;type=M;}
+  ~MNode(){inbound=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void setInbound(FIFO *fifo){inbound=fifo;}
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+};
+
+class DNode : public SDFNode{
+private:
+  /*number of samples to read at a time from input edge*/
+  int numOfSamples;
+  /*edge providing input to this node*/
+  FIFO *inbound;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  DNode(int k=-1, int n=0){id=k;numOfSamples=n;type=D;}
+  ~DNode(){inbound=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  int getNumOfSamples()const{return numOfSamples;}
+  virtual void execute();
+  virtual void display()const;
+  void setInbound(FIFO *fifo){inbound=fifo;}
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+};
+
+class UNode : public SDFNode{
+private:
+  /*number of samples to duplicate*/
+  int numOfCopies;
+  /*edge providing input to this node*/
+  FIFO *inbound;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  UNode(int k=-1, int n=0){id=k;numOfCopies=n;type=U;}
+  ~UNode(){inbound=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  int getNumOfCopies()const{return numOfCopies;}
+  virtual void execute();
+  virtual void display()const;
+  void setInbound(FIFO *fifo){inbound=fifo;}
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+};
+
+class CNode : public SDFNode{
+private:
+  /*constant value this node provides*/
+  const int constant;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  CNode(int k=-1, int c=0):constant(c){id=k;}
+  ~CNode(){}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+};
+
+class FNode : public SDFNode{
+private:
+  /*edge providing input to this node*/
+  FIFO *inbound;
+  /*edges going outward from this node*/
+  vector<FIFO*> outbounds;
+public:
+  FNode(int k=-1){id=k;type=F;}
+  ~FNode(){inbound=NULL;}
+  virtual int getId()const{return id;}
+  virtual NodeType getType()const{return type;}
+  virtual void execute();
+  virtual void display()const;
+  void setInbound(FIFO *fifo){inbound=fifo;}
+  void addOutbound(FIFO *fifo){outbounds.push_back(fifo);}
+};
+
+/*each edge is represented by a First-in-First-out queue, producer puts data into the queue, consumer removes data from the queue*/
+class FIFO{
+private:
+  /*id of the fifo*/
+  int id;
+  /*queue holding data*/
+  queue<int> fifo;
+  /*src is producer node, dst is consumer node*/
+  SDFNode *src, *dst;
+public:
+  int getData();
+  void putData(int d);
+  SDFNode *getSrc()const{return src;}
+  SDFNode *getDst()const{return dst;}
+  void setSrc(SDFNode *s){src=s;}
+  void setDst(SDFNode *d){dst=d;}
+  void display()const;
+  int getId()const{return id;}
+  int getSize()const{return fifo.size();}
+  FIFO(int k=-1):id(k),src(NULL),dst(NULL){}
+  ~FIFO(){src=dst=NULL;}
+};
+
+/*compressed topology matrix*/
+class TMatrixRow{
+private:
+  /*srcNode is the id of the producer node, dstNode is the id of the consumer node*/
+  int srcNode, dstNode;
+  /*tokensProduced is the number of tokens produced by producer, tokensConsumed is the number of tokens consumed by consumer*/
+  int tokensProduced, tokensConsumed;
+public:
+  TMatrixRow(int sn=-1, int pt=-1, int dn=-1, int ct=-1):srcNode(sn),dstNode(dn),tokensProduced(pt),tokensConsumed(ct){}
+  void setValue(int sn, int pt, int dn, int ct){srcNode=sn;tokensProduced=pt;dstNode=dn;tokensConsumed=ct;}
+  int getSrc()const{return srcNode;}
+  int getDst()const{return dstNode;}
+  int getTokensConsumed()const{return tokensConsumed;}
+  int getTokensProduced()const{return tokensProduced;}
+};
+
+/*synchronous data flow*/
+class SDFG{
+private:
+  /*input node, each sdf has one and only one input node*/
+  INode *gin;
+  /*output node, each sdf has one and only one output node*/
+  ONode *gout;
+  /*list of nodes (including gin and gout)*/
+  vector<SDFNode*> nodes;
+  /*list of FIFOs*/
+  vector<FIFO*> fifos;
+  /*topology matrix corresponding to this sdf*/
+  TMatrixRow topologyMatrix[256];
+  /*number of nodes in sdf, equals nodes.size()*/
+  int numOfNodes;
+  /*number of FIFOs in sdf, equals fifos.size()*/
+  int numOfFIFOs;
+  /*if hasSchedule() method has ever been called, this variable is intended to avoid recalculating hasSchedule() again*/
+  bool scheduleTested;
+  /*mark if this sdf is schedulable; together with scheduleTested variable, we can avoid recalculating hasSchedule()*/
+  bool schedulable;
+  /*schedule, for example, 1,2,4,3... means firing node 1 first, then 2, then 4, then 3*/
+  vector<int> schedule;
+  /*a vector storing the number of times each node has to fire in ONE schedule, e.g. numOfFiringRequired[0] is the
+    number of times node 0 has to fire in the schedule, numOfFiringRequired[1] is the number of times node 1 has to
+    fire in the schedule*/
+  vector<int> numOfFiringRequired;
+  /*mark if a schedule has been found*/
+  bool scheduleFound;
+public:
+  SDFG():gin(NULL),gout(NULL),numOfNodes(0),numOfFIFOs(0),scheduleTested(false),schedulable(false), scheduleFound(false){}
+  SDFG(char*, RingBuffer*, RingBuffer*);
+  ~SDFG();
+  INode *getInput()const{return this->gin;}
+  ONode *getOutput()const{return this->gout;}
+  void addNode(SDFNode *node);
+  //get the fifo with a specific id, if the fifo does not exist, create one and insert into fifos.
+  FIFO* getFIFO(int id);
+  vector<SDFNode *> getNodes()const{return this->nodes;}
+  SDFNode *getNodeAt(int i)const{return (i<this->nodes.size())? this->nodes[i]:NULL;}
+  //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
+  FIFO *getFIFOAt(int i)const{return (i<this->fifos.size()) ? this->fifos[i]:NULL;}
+  vector<FIFO *> getFIFOs()const{return this->fifos;}
+  int getNumOfNodes()const{return this->numOfNodes;}
+  void setNumOfNodes(int k){numOfNodes=k;}
+  int getNumOfFIFOs()const{return this->numOfFIFOs;}
+  void setNumOfFIFOs(int k){numOfFIFOs=k;}
+  //create node of specific kind
+  void getINode(int nodeId, int params[], int count);
+  void getONode(int nodeId, int params[], int count);
+  void getANode(int nodeId, int params[], int count);
+  void getSNode(int nodeId, int params[], int count);
+  void getMNode(int nodeId, int params[], int count);
+  void getDNode(int nodeId, int params[], int count);
+  void getUNode(int nodeId, int params[], int count);
+  void getCNode(int nodeId, int params[], int count);
+  void getFNode(int nodeId, int params[], int count);
+  void addDelay(int params[], int count);
+  //build compressed topology matrix, compressing the columns
+  void buildTopologyMatrix();
+  void printTopologyMatrix()const;
+  /*calling sequence: hasSchedule<makeSchedule<execute*/
+  bool hasSchedule();
+  vector<int> getNumOfFiringRequired()const{return numOfFiringRequired;}
+  void printNumOfFiringRequired()const;
+  void makeSchedule();
+  void printSchedule()const;
+  void setInput(RingBuffer *data);
+  void setOutput(RingBuffer *buf);
+  void execute(int numOfRepetions);
+  int getChecksum()const{return gout->getChecksum();}
+};
+#endif
\ No newline at end of file