Loading ...
Sorry, an error occurred while loading the content.

Managing a network of nodes and data streams in one thread

Expand Messages
  • Jim Peters
    Here is a plan, roughly expressed in Java. (For Dave, in Java every mention of a classname is a pointer -- so these are pointers not in-line objects): class
    Message 1 of 13 , Mar 21, 2002
    • 0 Attachment
      Here is a plan, roughly expressed in Java. (For Dave, in Java every
      mention of a classname is a pointer -- so these are pointers not
      in-line objects):

      class Node {
      InPort in[];
      OutPort out[];
      void process() {};
      };

      class InPort {
      OutPort link;
      int cnt;
      };

      class OutPort {
      double val;
      int cnt;
      };

      It works like this: Every object that is interested in sending data
      out or receiving data in inherits from Node. This allows it to set up
      a list of its input and output ports. It, or some other code, can
      then connect the input ports to the output ports of other Nodes by
      setting the 'link' member of the InPort.

      Node-supervisor code somewhere can keep a list of all Nodes and scan
      them to see which depend on which others through their InPort 'link'
      members. It can then sort them into an order that makes sure that
      nothing gets run before data is available for it. So long as we are
      not permitting feedback loops, this is easy.

      The procedure for outputting data goes like this:

      - Put a new value into out[nn].val
      - Increment out[nn].cnt

      That way anyone watching knows that a new value is available.

      The Node-supervisor code can check to see if the OutPort 'cnt' value
      differs from the in[nn].cnt value for any InPort pointing to it
      through its in[nn].link. If it differs, then there is new data for
      that InPort, which means that the Node process() function should be
      called. The Node handling code can update the in[nn].cnt values to
      match the linked-to out[nn].cnt value (i.e. in[nn].link.cnt) after the
      Node process() call has returned.

      The Node-supervisor code only ever has to run through its list of
      Nodes in the sorted order it worked out initially, because this
      guarantees that it will pick up all the Nodes that need to run in the
      correct order for them to make data available for later Nodes.

      For a simple Node that only handles a set of InPorts all at a single
      rate, all it has to do in process() is read the in[nn].link.val value
      for all its inputs, without worrying about in[nn].cnt, since the
      Node-supervisor code will have made sure that everything is ready.

      However, if the Node accepts several inputs that might be at different
      rates (e.g. EEG and temperature), then it needs to check that
      in[nn].cnt != in[nn].link.cnt before reading the value.

      That's it, pretty well.

      Unlike Dave's system, this is only useful for interconnecting things
      within memory, and within the same thread. In that sense it is less
      flexible, but faster. It also assumes that data streams are split up
      into individual streams of floating point values.

      This is all just the basic level -- we could extend this to allow a
      Node to give short labels to its input and output ports so that they
      are easier to identify using names rather than numbers, which might
      allow the interconnections to be setup more easily from a config file.
      Also the Nodes themselves could be given short labels when they are
      created.

      I guess someone will want to write lots of wrapper functions with long
      names to encode what I just outlined. It seems really unnecessary to
      me, but if that's what makes people happy ...


      So, does this fit in with what other people were planning ?


      [ I know Dave is away until next week sometime, but I thought I'd
      write this anyway whilst I had it in my head. ]

      Jim

      --
      Jim Peters (_)/=\~/_(_) jim@...
      (_) /=\ ~/_ (_)
      Uazú (_) /=\ ~/_ (_) http://
      B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
    • Dave
      On Thu, 21 Mar 2002 15:17:57 +0000, Jim Peters wrote: Hey Jim--I have several questions concerning your byte stream replacement data model. ... In OutPort,
      Message 2 of 13 , Mar 27, 2002
      • 0 Attachment
        On Thu, 21 Mar 2002 15:17:57 +0000, Jim Peters wrote:

        Hey Jim--I have several questions concerning your "byte stream" replacement
        data model.

        >class Node {
        > InPort in[];
        > OutPort out[];
        > void process() {};
        >};
        >
        >class InPort {
        > OutPort link;
        > int cnt;
        >};
        >
        >class OutPort {
        > double val;
        > int cnt;
        >};

        In OutPort, you have one single 'val' and a 'cnt'. What does 'cnt' refer to?
        Since 'val' is not an array or pointer, I am not sure how 'cnt' is being used.
        Is this just a sequence counter for the out[] array of sample values? But
        below you mention that when you want to add a value, you stuff it in
        out[nn].val and increment out[nn].cnt. What is 'nn' -- the next spot on the
        stack to push a sample value? In that case, 'cnt' for that out[nn].val would
        always be 1, since it is a new push. I dunno; I think I am not understanding
        the implementation clearly.

        Also, am I right in assuming that the Sensor class would inherit Node since
        these are the classes interested in sending data? If that is the case, is it
        necessary for every Node to have an InPort link, or can that be null to
        indicate that there is no input link?

        >It works like this: Every object that is interested in sending data
        >out or receiving data in inherits from Node. This allows it to set up
        >a list of its input and output ports. It, or some other code, can
        >then connect the input ports to the output ports of other Nodes by
        >setting the 'link' member of the InPort.

        Can you give some concrete examples of what that input/output linkage would
        look like using sensor data and/or dsp processing? Could you give one or more
        real life case examples to help me ground my understanding?

        >Node-supervisor code somewhere can keep a list of all Nodes and scan
        >them to see which depend on which others through their InPort 'link'

        Would the Node-supervisor be a part of BioDevice, in that it sits waiting for
        data from the device, and then scans the node list to see who gets what?

        >members. It can then sort them into an order that makes sure that
        >nothing gets run before data is available for it. So long as we are
        >not permitting feedback loops, this is easy.
        >
        >The procedure for outputting data goes like this:
        >
        >- Put a new value into out[nn].val
        >- Increment out[nn].cnt
        >
        >That way anyone watching knows that a new value is available.

        How does one watch for new values? Is this done by viture of the fact that
        they have added themselves as a Node to the node list with their own process()
        routine? Is this similar to the MVC pattern which registers several callback
        views via an update() routine for a given resource? Is this watching triggered
        by a wait state on select()? ??

        >The Node-supervisor code can check to see if the OutPort 'cnt' value
        >differs from the in[nn].cnt value for any InPort pointing to it
        >through its in[nn].link. If it differs, then there is new data for
        >that InPort, which means that the Node process() function should be
        >called. The Node handling code can update the in[nn].cnt values to
        >match the linked-to out[nn].cnt value (i.e. in[nn].link.cnt) after the
        >Node process() call has returned.

        So, in other words, at some point the Node-supervisor does a dependency check
        for all output ports that have linked input ports to make sure that waiting
        output data has actually been sent through the InPort link mechanism?

        Also, just what does the process() method do? Is this a virtual method
        dependent on just what the Node needs to do with the data (such as display it,
        do some mathematical processing on it, such as FFT filtering, or somesuch)? Or
        is process() a function that simply moves the floating piont value from
        out[nn].val to in[nn].link.val and update the 'cnt's?

        >Unlike Dave's system, this is only useful for interconnecting things
        >within memory, and within the same thread. In that sense it is less
        >flexible, but faster. It also assumes that data streams are split up
        >into individual streams of floating point values.

        I'll be better able to speak to this to see after I have a better grasp of your
        proposal, and see if there is a way to use the process() method as a means to
        transfer data in other ways, perhaps as a callback function to a socket or
        somesuch. I like what you outline as it does have a lot less overhead than the
        block-and-unblock method of threads and other sharing mechanisms.

        >This is all just the basic level -- we could extend this to allow a
        >Node to give short labels to its input and output ports so that they
        >are easier to identify using names rather than numbers, which might
        >allow the interconnections to be setup more easily from a config file.
        >Also the Nodes themselves could be given short labels when they are
        >created.
        >
        >I guess someone will want to write lots of wrapper functions with long
        >names to encode what I just outlined. It seems really unnecessary to
        >me, but if that's what makes people happy ...

        Well, gotta tell you. Those names to encode what you outlined sure would help
        this visually oriented person. We simply have different learning and
        comprehension styles. Personally, I marvel at someone capable of purely
        abstract and logical thought. I tend to think in pictures and descriptions,
        and while abstract logic is part-and-parcel of our work, it is not "first
        nature" for me. So I'll be the first to write a few wrapper functions... :)

        Dave.
      • Jim Peters
        ... Okay, I m working on the idea that there is no buffering between the parts of the system. So we only ever need to store a single value -- the current
        Message 3 of 13 , Mar 27, 2002
        • 0 Attachment
          Dave wrote:
          > Hey Jim--I have several questions concerning your "byte stream" replacement
          > data model.
          >
          > >class Node {
          > > InPort in[];
          > > OutPort out[];
          > > void process() {};
          > >};
          > >
          > >class InPort {
          > > OutPort link;
          > > int cnt;
          > >};
          > >
          > >class OutPort {
          > > double val;
          > > int cnt;
          > >};
          >
          > In OutPort, you have one single 'val' and a 'cnt'. What does 'cnt'
          > refer to? Since 'val' is not an array or pointer, I am not sure how
          > 'cnt' is being used.

          Okay, I'm working on the idea that there is no buffering between the
          parts of the system. So we only ever need to store a single value --
          the current value. Since different data streams might go at different
          rates, we also need some way to indicate whether the 'val' value is a
          new one, or the same one we saw last time around. This is why I'm
          having a 'cnt' counter value, which changes every time a new value
          goes into 'val'.

          Anyone watching an OutPort keeps a copy of 'cnt' from the last time
          they looked. At some later point, if 'cnt' has changed since the last
          time they looked, then there must be a new value there to process.

          > What is 'nn' -- the next spot on the stack to push a sample value?

          No, there is no stack. Each 'nn' is a different output stream. The
          whole idea was that each 'Node' would have a set of input streams, and
          a set of output streams.

          > Also, am I right in assuming that the Sensor class would inherit
          > Node since these are the classes interested in sending data?

          I really don't know about the best way to set up an inheritance graph.
          I would guess that you can say "a Sensor is a Node", so that probably
          means it should inherit ... !?

          > If that is the case, is it necessary for every Node to have an
          > InPort link, or can that be null to indicate that there is no input
          > link?

          Well, maybe this needs to be expressed differently in C++. The idea
          was that you could have an array of zero InPorts if you don't actually
          need any. I don't know about how to do arrays 'nicely' in C++, but in
          C, it could all be done like this:

          typedef struct InPort InPort;
          typedef struct OutPort OutPort;
          typedef struct Node Node;

          struct InPort {
          OutPort *link;
          int cnt;
          };

          struct OutPort {
          double val;
          int cnt;
          };

          struct Node {
          int n_in; // Number of input streams, or 0
          InPort *in; // Pointer to allocated array of 'n_in' InPort structures
          int n_out; // Number of output streams, or 0
          OutPort *out; // Pointer to allocated array of 'n_out' OutPort structures
          void (*process)();
          };

          > Can you give some concrete examples of what that input/output
          > linkage would look like using sensor data and/or dsp processing?
          > Could you give one or more real life case examples to help me ground
          > my understanding?

          Okay, let's say we have a Sensor that is generating two channels of
          data, a FilterBank that converts a single input stream into a set of
          output streams (16 in this example), and a 'Christmas tree' display
          module which accepts two sets of 16 inputs to display a double
          bar-graph up the screen. I'll write this in pseudo-C, because my C++
          knowledge is not too strong.

          Sensor *dev= sensor_new("/dev/ttyS1", "prograph/9600", ... etc ...);
          FBank *fb1= fbank_new(16, 1.0, 16.0); // 16 filters between 1Hz and 16Hz
          FBank *fb2= fbank_new(16, 1.0, 16.0); // 16 filters between 1Hz and 16Hz
          XmasDisp *xmas= xmas_new(16, ... display details, whatever ...);

          // Connect filterbank inputs to the first two 'dev' output channels
          fb1->in[0].link= &dev->out[0];
          fb2->in[0].link= &dev->out[1];

          // Connect display inputs to filterbank outputs -- pretend that
          // ordering of display inputs is top-bottom, L/R/L/R, i.e. interleaved
          // and upside-down compared to the filterbank outputs
          for (int a= 0; a<32; a++) {
          FBank *fb= (a&1) ? fb2 : fb1;
          int n= 15 - a/2;
          xmas->in[a].link= &fb->out[n];
          }

          That's it. When this network comes to be executed, the Node handling
          code would do this sequence of calls for every input sample:

          dev->process();
          fb1->process();
          fb2->process();
          xmas->process();

          In this case everything is simple, because all the data rates are the
          same, so nothing really has to care about the 'cnt' values. However,
          if channel 'B' (dev->out[1], say) only outputs data at 16Hz compared
          to 256Hz for channel 'A' (dev->out[0]), then fb2->process() would only
          get called once in every 16 calls to fb1->process(), and
          xmas->process() would have to be aware that most of the time it is
          only getting new values on half of its inputs and not on all of them
          (although for display purposes, it isn't much of a problem if it keeps
          on using the values without checking).

          For display Nodes, I suggest that they keep a data structure somewhere
          containing the current data to display, and on the ->process() call,
          they update that data and then set a flag for some other thread to
          actually do the redraw. That way it doesn't matter if the front-end
          can only update for 1 in every 20 samples. With a little bit of care,
          this makes the whole thing rock-solid, so it can work 100% reliably
          even when there are large redraws or whatever to slow down the
          front-end.


          > >Node-supervisor code somewhere can keep a list of all Nodes and scan
          > >them to see which depend on which others through their InPort 'link'
          >
          > Would the Node-supervisor be a part of BioDevice, in that it sits
          > waiting for data from the device, and then scans the node list to
          > see who gets what?

          I'm seeing the Node supervisor code as part of the Node class,
          represented by a few class-global functions and variables (I can't
          remember whether C++ has this -- it must do, surely. Are they
          'static' ?).

          I know what you're saying -- how does the network get kicked off in
          the first place ? This is another question, separate in some ways
          from the question of how to connect up the network itself.

          Here is one approach: we could say that anything that has outputs but
          no inputs must obviously create data from some external source, in
          which case it always gets called to trigger off a new cycle. Nodes
          that have no inputs could be written in such a way that they block
          until they have some data for us. Once the ->process() call returns,
          then the rest of the network runs through with the new data, until
          execution again returns to input device ->process() call to wait for
          some more.

          This is just one way we could approach it -- we could accomodate more
          complex scenarios as well. This really depends on how we might choose
          to arrange our threads and so on.


          > >The procedure for outputting data goes like this:
          > >
          > >- Put a new value into out[nn].val
          > >- Increment out[nn].cnt
          > >
          > >That way anyone watching knows that a new value is available.
          >
          > How does one watch for new values? Is this done by viture of the
          > fact that they have added themselves as a Node to the node list with
          > their own process() routine? Is this similar to the MVC pattern
          > which registers several callback views via an update() routine for a
          > given resource? Is this watching triggered by a wait state on
          > select()? ??

          In my plan each Node is known about by the Node-supervisor code --
          most probably it would be linked into a list maintained by that code,
          or stored in an array maintained by that code. That way, the
          node-supervisor code knows when a Node has new data waiting by
          observing the counter values at either end of the link. If the 'cnt'
          values are the same for an InPort, then there is no new data,
          otherwise there is.

          'select()' is of no use, as we are not using different threads, nor
          UNIX pipes or anything like that. Also, we are not registering any
          callbacks with anything, because an individual Node knows nothing
          about which other Nodes have ->link pointers pointing to its outputs.
          However, the Node-supervisor code knows about all the active Nodes, so
          it can watch over the whole thing easily without needing to use a
          callback mechanism.


          > So, in other words, at some point the Node-supervisor does a
          > dependency check for all output ports that have linked input ports
          > to make sure that waiting output data has actually been sent through
          > the InPort link mechanism?

          Yes.

          > Also, just what does the process() method do? Is this a virtual
          > method dependent on just what the Node needs to do with the data
          > (such as display it, do some mathematical processing on it, such as
          > FFT filtering, or somesuch)? Or is process() a function that simply
          > moves the floating piont value from out[nn].val to in[nn].link.val
          > and update the 'cnt's?

          The ->process() method does the actual processing that the Node is
          there for -- as you say, reading the device, filtering data streams,
          data display, or whatever.

          There are no values stored in the InPort arrays -- in[nn].link.val (or
          in[nn].link->val in C) is actually a value from the 'out' array of
          another Node (the .link member is an OutPort pointer).

          > I'll be better able to speak to this to see after I have a better
          > grasp of your proposal, and see if there is a way to use the
          > process() method as a means to transfer data in other ways, perhaps
          > as a callback function to a socket or somesuch. I like what you
          > outline as it does have a lot less overhead than the
          > block-and-unblock method of threads and other sharing mechanisms.

          Certainly a process() method could be used to send output to a pipe or
          socket, so long as there isn't much chance of it blocking (or else it
          would hold other things up). If we were going to allow several Nodes
          to read from different input devices, e.g. several sockets and/or
          serial streams, then we would need some additional code that does a
          big select(), before triggering whichever Node has waiting data.

          > >I guess someone will want to write lots of wrapper functions with long
          > >names to encode what I just outlined. It seems really unnecessary to
          > >me, but if that's what makes people happy ...
          >
          > Well, gotta tell you. Those names to encode what you outlined sure
          > would help this visually oriented person. We simply have different
          > learning and comprehension styles. Personally, I marvel at someone
          > capable of purely abstract and logical thought. I tend to think in
          > pictures and descriptions, and while abstract logic is
          > part-and-parcel of our work, it is not "first nature" for me. So
          > I'll be the first to write a few wrapper functions... :)

          Okay, no problem. It just seems a shame to hide such a simple
          mechanism underneath an abstraction layer. People coming to a class
          interface often have no idea what is really going on underneath. It
          could be some incredibly inefficient mechanism, or as in this case,
          something that could compile down to a couple of inlined instructions
          per call.

          Personally, when I come across interface documentation, I really
          appreciate it when people outline the underlying mechanism. I feel
          uncomfortable using any interface where I don't know (or can't easily
          guess) the underlying mechanism. How am I supposed to make good
          coding decisions when I don't know the implications of different
          approaches ?

          Well, that's just my personal frustration with 'object-oriented'
          coding (or perhaps 'wrapper-oriented' coding), but never mind.

          Anyway, I'm not going to argue about this (apart from grumbling a
          bit), and I will accept the use of wrapper functions if it will make
          things more conventional and predictable for C++ programmers.

          Jim

          --
          Jim Peters (_)/=\~/_(_) jim@...
          (_) /=\ ~/_ (_)
          Uazú (_) /=\ ~/_ (_) http://
          B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
        • John Morrison
          I ve been having a think about the idea since it was put up and I do like it as we should reduce contact switching as much as possible. Though I think there
          Message 4 of 13 , Mar 28, 2002
          • 0 Attachment
            I've been having a think about the idea since it was put up and I do like it
            as we should reduce contact switching as much as possible. Though I "think"
            there "maybe" problems too.

            MY ANALYSIS
            So as I understand it a data byte arrives at the device which in some way
            triggers the "network" which executes the following actions.
            > dev->process();
            > fb1->process();
            > fb2->process();
            > xmas->process();
            Sounds great (I do like the idea) until we realise it's a REAL TIME system
            we are working toward.

            So lets plug some (Made UP) figures into this system and apply some
            restrictions and assumptions to the system.

            Assumptions
            ALL inputs and outputs aren't buffered and can only hold 1 byte of data at
            a time.
            TI = Time Interval

            Timings (No basis in reality just for demonstration)
            DEV
            Input arrives every 1 TI
            stay valid for .5 TI
            Process takes .5 TI

            FD1/2
            Process takes .5 TI

            xmas
            Process takes .5 TI

            Timing Chart

            DEV FD1 FD2 Xmas
            Time Input Process Output Process Output Process Output Process Display
            00.0
            00.5
            01.0 1 Y
            01.5 1 Y
            02.0 2 1 1 Y
            02.5 1 1 1 Y
            03.0 3 Y 1 1 1 1 1
            03.5 3 Y 1 1 1 1
            04.0 4 3 3 Y 3 1 1
            04.5 3 3 3 Y 1 1
            05.0 5 Y 3 3 3 3 3
            05.5 5 Y 3 3 3 3
            06.0 6 5 5 Y 5 3 3
            06.5 5 5 5 Y 3 3
            07.0 7 Y 5 5 5 5 5
            07.5 7 Y 5 5 5 5
            08.0 8 7 7 Y 7 5 5
            08.5 7 7 7 Y 5 5
            09.0 9 Y 7 7 7 7 7
            09.5 9 Y 7 7 7 7
            10.0 10 9 9 Y 9 7 7
            10.5 9 9 9 Y 7 7
            11.0 11 Y 9 9 9 9 9

            So for this system using these figures we loose every second byte. :-(
            Of course this gets worse the longer the chain.

            I do like the idea and if I've made a mistake please correct it and explain
            where I went wrong!

            If not I'll send an alternate/Hybrid proposal tonight (next 2 hours) for
            your examination.

            John
          • Jim Peters
            ... If the processing for every sample takes longer than the interval between samples, then we are stuffed in any case -- even if we had a different networking
            Message 5 of 13 , Mar 28, 2002
            • 0 Attachment
              John Morrison wrote:
              > I've been having a think about the idea since it was put up and I do like it
              > as we should reduce contact switching as much as possible. Though I "think"
              > there "maybe" problems too.
              >
              > MY ANALYSIS
              > So as I understand it a data byte arrives at the device which in some way
              > triggers the "network" which executes the following actions.
              > > dev->process();
              > > fb1->process();
              > > fb2->process();
              > > xmas->process();
              > Sounds great (I do like the idea) until we realise it's a REAL TIME system
              > we are working toward.
              >
              > So lets plug some (Made UP) figures into this system and apply some
              > restrictions and assumptions to the system.
              >
              > Assumptions
              > ALL inputs and outputs aren't buffered and can only hold 1 byte of data at
              > a time.
              > TI = Time Interval
              >
              > Timings (No basis in reality just for demonstration)
              > DEV
              > Input arrives every 1 TI
              > stay valid for .5 TI
              > Process takes .5 TI
              >
              > FD1/2
              > Process takes .5 TI
              >
              > xmas
              > Process takes .5 TI

              If the processing for every sample takes longer than the interval
              between samples, then we are stuffed in any case -- even if we had a
              different networking model, or huge buffers, the processing would just
              get farther and farther behind the input.

              So, in your model, the total processing must be less than 1 TI,
              whichever way we arrange the networking code. If it doesn't, then
              your computer simply isn't fast enough to do what you want to do.

              The only way around this is to do what you do when you are handing
              audio, and that is to optimise the processing code by breaking up the
              audio into 64-sample (or larger) chunks, which are faster to process
              and pass around. However, in our situation, dealing with data at
              256Hz, say, working in 64-sample chunks results in a 250ms delay.

              For the kind of data rates we're using (e.g. 256Hz, rather than audio
              rates of 44100Hz), I think processing one sample at a time would be
              quite feasible. Working in chunks of 4 or 8 samples might also be
              do-able, which could give a small increase in speed, but I don't think
              it is worth the extra coding complexity and signal delays. Also, it
              really would start getting messy if we tried to handle signals with
              different sampling rates in 4-sample chunks (e.g. 16Hz and 256Hz).

              As a guide to the processing power required, imagine what kind of spec
              machine you would need to run a network in one of those audio plugin
              platforms like Buzz or Cubase, and then remember that we're dealing
              with data at roughly 1/100th of the sampling rate. So we don't need
              *that* powerful a machine to do what we want to do.

              I hope this helps --

              Jim

              --
              Jim Peters (_)/=\~/_(_) jim@...
              (_) /=\ ~/_ (_)
              Uazú (_) /=\ ~/_ (_) http://
              B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
            • Dave
              ... And then just have this value wrap back to zero when the integer maxes out (INT_MAX, or UINT_MAX if unsigned)? I am a bit concerned about doing this
              Message 6 of 13 , Mar 28, 2002
              • 0 Attachment
                On Wed, 27 Mar 2002 23:35:35 +0000, Jim Peters wrote:

                >> In OutPort, you have one single 'val' and a 'cnt'. What does 'cnt'
                >> refer to? Since 'val' is not an array or pointer, I am not sure how
                >> 'cnt' is being used.
                >
                >Okay, I'm working on the idea that there is no buffering between the
                >parts of the system. So we only ever need to store a single value --
                >the current value. Since different data streams might go at different
                >rates, we also need some way to indicate whether the 'val' value is a
                >new one, or the same one we saw last time around. This is why I'm
                >having a 'cnt' counter value, which changes every time a new value
                >goes into 'val'.

                And then just have this value wrap back to zero when the integer maxes out
                (INT_MAX, or UINT_MAX if unsigned)? I am a bit concerned about doing this
                unbuffered, and would want to throw together some tests to see what happens
                when we scale it upwards by adding more and more process() calls. As long as
                the combined process() calls are faster than the rate at which data is
                streaming, all would be fine. I suppose that would hold true for any amount of
                processing we did, so buffered or unbuffered, we are going to have to handle
                the data faster than it comes in. I dunno; it will take a few tests to find
                out if this is an issue or not.

                >Anyone watching an OutPort keeps a copy of 'cnt' from the last time
                >they looked. At some later point, if 'cnt' has changed since the last
                >time they looked, then there must be a new value there to process.
                >
                >> What is 'nn' -- the next spot on the stack to push a sample value?
                >
                >No, there is no stack. Each 'nn' is a different output stream. The
                >whole idea was that each 'Node' would have a set of input streams, and
                >a set of output streams.

                What I think you have, then, is a variation on the MVC paradigm. In this case,
                the "model" is your Node-supervisory code which knows about the data and all
                the "views" attached to the data. The attached observer views and their
                update() calls would be akin to your linked Nodes with their process() calls.
                However, MVC uses a notification system to the views, telling them when new
                data is available. And, as I understand it, it is up to each view to then to
                call the model to actually get the updated data. This is different from your
                idea where the model (i.e., node-supervisor) would be respondible for calling
                the update() views directly.

                But, since no one else is jumping in to help flesh out the use of MVC in the
                context of this project and my previous MVC questions have gone unanswered, I'm
                going to have to let it drop.

                >> Also, am I right in assuming that the Sensor class would inherit
                >> Node since these are the classes interested in sending data?
                >
                >I really don't know about the best way to set up an inheritance graph.
                >I would guess that you can say "a Sensor is a Node", so that probably
                >means it should inherit ... !?

                I don't know.... because if we say that, then the definition of a Sensor
                changes in that a sensor object now also takes on the meaning and function that
                is in the Device class. Perhaps it is more accurate to say that any object
                which produces or receives real time sample data inherits the Node class.
                Thus, the BioDevice class would inherit Node. It would be up to BioDevice to
                add the correct number of out[nn] data streams.

                >> If that is the case, is it necessary for every Node to have an
                >> InPort link, or can that be null to indicate that there is no input
                >> link?
                >
                >Well, maybe this needs to be expressed differently in C++. The idea
                >was that you could have an array of zero InPorts if you don't actually
                >need any. I don't know about how to do arrays 'nicely' in C++, but in
                >C, it could all be done like this:

                Arrays can be done in the same was as in C, either as directly allocated using
                brackets [], or via a pointer to allocated memory. Or, you can let an STL
                template manage the array using lists, vectors, etc., depending on how you need
                access to the array. I have a better understanding now on what you were
                writing in Java (and why you mentioned that classnames were pointers). It
                could look like this in C++:

                #include <vector>

                class OutPort {
                double val;
                int cnt;
                };

                class InPort {
                OutPort *link;
                int cnt;
                };

                class Node {
                private:
                std::vector<InPort*> in;
                std::vector<OutPort*> out;
                public:
                virtual void process() = 0;
                };

                Gotta admit that Java's expression of the array was a whole lot nicer.

                >> Can you give some concrete examples of what that input/output
                >> linkage would look like using sensor data and/or dsp processing?
                >> Could you give one or more real life case examples to help me ground
                >> my understanding?
                >
                >Okay, let's say we have a Sensor that is generating two channels of
                >data, a FilterBank that converts a single input stream into a set of
                >output streams (16 in this example), and a 'Christmas tree' display
                >module which accepts two sets of 16 inputs to display a double
                >bar-graph up the screen.

                Ok; thanks--your description is very helpful.

                > Sensor *dev= sensor_new("/dev/ttyS1", "prograph/9600", ... etc ...);

                I think that the above should not be a "Sensor," but instead "Device" -- or
                more pointedly, BioDevice. This might simply be a difference in the use in
                terminology, but I think it is important to clear up. The physical correlate
                of a BioSensor is an electrode/wire. Thus, a BioDevice will have one more more
                BioSensors. When you say above that "a Sensor is generating two channels of
                data," I think that shoud really read as "a BioDevice is generating two
                channels of data." This makes a difference in the way we use our BioDevice and
                BioSensor objects internally. It also helps keep behavior and function
                separate based on what we want to interact with -- a BioDevice or a BioSensor.

                > FBank *fb1= fbank_new(16, 1.0, 16.0); // 16 filters between 1Hz and 16Hz
                > FBank *fb2= fbank_new(16, 1.0, 16.0); // 16 filters between 1Hz and 16Hz
                > XmasDisp *xmas= xmas_new(16, ... display details, whatever ...);

                What I like about your plan is the patch-chord kind of arrangment of the
                objects, where you can daisy-chain input and outputs together in a variety of
                configurations. This could keep data flows very flexible based on what may be
                needed later on down the line in terms of biofeedback protocols. What I would
                like to see is it more situated within the BioDevice/BioSensor framework. This
                would alleviate the need for node-supervisory code being in the node code (as
                globals or whatever), and keep the flow more natural in terms of the system.

                For example, we've already touched on the issue of what kicks the whole network
                into motion. The natural starting place for that kick-off would be when data
                is received from a sensor. This is controlled by the BioDevice object, which
                reads the raw data stream in from the port/device and is able to separate it
                out into individual sensor streams for our use (or, plug one byte at a time
                into a receiving node as per your plan -- I am using the word "stream" here
                loosely). Otherwise, where (or who) would start the traversal of the node/port
                tree? If I am understanding correctly, that traversal will only occur when
                there is data ready from the external device for a particular port in the node
                list. Are there are other situations I'm not thinking of?

                > // Connect filterbank inputs to the first two 'dev' output channels
                > fb1->in[0].link= &dev->out[0];
                > fb2->in[0].link= &dev->out[1];
                >
                > // Connect display inputs to filterbank outputs -- pretend that
                > // ordering of display inputs is top-bottom, L/R/L/R, i.e. interleaved
                > // and upside-down compared to the filterbank outputs
                > for (int a= 0; a<32; a++) {
                > FBank *fb= (a&1) ? fb2 : fb1;
                > int n= 15 - a/2;
                > xmas->in[a].link= &fb->out[n];
                > }
                >
                >That's it. When this network comes to be executed, the Node handling
                >code would do this sequence of calls for every input sample:
                >
                > dev->process();
                > fb1->process();
                > fb2->process();
                > xmas->process();

                Ok... except dev, fb1, fb2, and xmas would really be pointers kept in a list
                which would then be controlled by the node-supervisory code, right? The more I
                think about this, the more it seems like there should be a Network class to
                handle traversal of the nodes as well as adding or removing nodes from the
                list, or that traversal should only be done from the BioDevice class when new
                data arrives for a particular sensor.

                >For display Nodes, I suggest that they keep a data structure somewhere
                >containing the current data to display, and on the ->process() call,
                >they update that data and then set a flag for some other thread to
                >actually do the redraw. That way it doesn't matter if the front-end
                >can only update for 1 in every 20 samples. With a little bit of care,
                >this makes the whole thing rock-solid, so it can work 100% reliably
                >even when there are large redraws or whatever to slow down the
                >front-end.

                Hmmm... that sound feasible. That type of arrangement (setting an event flag
                for another thread context) could be used for any processor that was going to
                slow things down.

                >> >Node-supervisor code somewhere can keep a list of all Nodes and scan
                >> >them to see which depend on which others through their InPort 'link'
                >>
                >> Would the Node-supervisor be a part of BioDevice, in that it sits
                >> waiting for data from the device, and then scans the node list to
                >> see who gets what?
                >
                >I'm seeing the Node supervisor code as part of the Node class,
                >represented by a few class-global functions and variables (I can't
                >remember whether C++ has this -- it must do, surely. Are they
                >'static' ?).

                Yes, static variables still exist, and, if declared static in a class, will be
                shared amongst all objects instantiated from that class. I see how you are
                thinking about this, and that would be a great way to keep a list of the entire
                network tree. As you mentioned in another message, this would only work,
                though, for one thread since you would not want to have some object adding a
                link to the list while another one was busy traversing the tree. If we do need
                to add some synchronization mechanisms, things like semaphores offer low
                overhead for this.

                >I know what you're saying -- how does the network get kicked off in
                >the first place ? This is another question, separate in some ways
                >from the question of how to connect up the network itself.

                >Here is one approach: we could say that anything that has outputs but
                >no inputs must obviously create data from some external source, in
                >which case it always gets called to trigger off a new cycle. Nodes
                >that have no inputs could be written in such a way that they block
                >until they have some data for us. Once the ->process() call returns,
                >then the rest of the network runs through with the new data, until
                >execution again returns to input device ->process() call to wait for
                >some more.

                Would we ever have more than one node that is a "producer only" node (meaning a
                node which only has a set of outputs, and no inputs because it receives data
                from an external source)? Based on prior discussions, it seemed like others
                were not in favor of building in support for multiple devices, thus I am not
                sure under what conditions there would be a reason to have more than one
                producer node in the network. I would not mind having the flexibility of
                adding such capability, but am thinking that this will effect the answer to the
                question of who kicks off the traversal of the network when new data arrives.

                >Certainly a process() method could be used to send output to a pipe or
                >socket, so long as there isn't much chance of it blocking (or else it
                >would hold other things up). If we were going to allow several Nodes
                >to read from different input devices, e.g. several sockets and/or
                >serial streams, then we would need some additional code that does a
                >big select(), before triggering whichever Node has waiting data.

                Right now the way I see it is that the whole process will block until data is
                received from the external device (in BioDevice). I can see that there would
                be ways to extend this design later on if I or someone else really wants
                multiple device support.

                >Well, that's just my personal frustration with 'object-oriented'
                >coding (or perhaps 'wrapper-oriented' coding), but never mind.
                >
                >Anyway, I'm not going to argue about this (apart from grumbling a
                >bit), and I will accept the use of wrapper functions if it will make
                >things more conventional and predictable for C++ programmers.

                You grumble so nicely, though. :) I hear everything you say, and yes, OO can
                certainly add some "wordy" overhead through abstraction layers. But it also
                makes it a bit more readable and descriptive. For example

                BioDeviceProComp procomp;
                FilterBank filterbank1;

                filterbank1.AddInputPort( procomp.GetOutputPort(chan) )

                says a bit more than

                fb1->in[0].link= &dev->out[0]

                and gives us the ability to make changes to the add/get methods if need be.
                And, true, they may always remain just one line of code which could compile
                down to an inline statement. It's a trade-off, to be sure.

                What's nice is having the best of both worlds -- the abstraction for separation
                of the implementation details and ease-of-use and the source so that we can
                still lift the hood and check to see just how the engine is designed.
                Fortunately, we have both here.

                Dave.
              • John Morrison
                I ll give a better answer next time as I m just about out the door for a break away a few days. I d like to see Buffers in the system in case of variable
                Message 7 of 13 , Mar 28, 2002
                • 0 Attachment
                  I'll give a better answer next time as I'm just about out the door for a
                  break away a few days.

                  I'd like to see Buffers in the system in case of "variable" processing
                  times. A process may take a long time (Graphics) on one call and no time on
                  the next so could "Catch up" if necessary.

                  Processing power is probably enough to handle it BUT!
                  Tests of a scaled up system is the ONLY real way to check........

                  Even with context switching I'd prefer to see A high priority thread running
                  device Input then dropping it into a buffer.

                  From then on the processing model would be FINE as we can't loose data or
                  each process could "decide" to loose data if the buffer is building.

                  Anyway see you all in a few days. :-)
                  John


                  > -----Original Message-----
                  > From: Jim Peters [mailto:jim@...]
                  > Sent: Friday, 29 March 2002 7:10 AM
                  > To: buildcheapeeg@yahoogroups.com
                  > Subject: Re: [buildcheapeeg] Managing a network of nodes and data
                  > streams in one thread
                  >
                  >
                  > John Morrison wrote:
                  > > I've been having a think about the idea since it was put up and
                  > I do like it
                  > > as we should reduce contact switching as much as possible.
                  > Though I "think"
                  > > there "maybe" problems too.
                  > >
                  > > MY ANALYSIS
                  > > So as I understand it a data byte arrives at the device which
                  > in some way
                  > > triggers the "network" which executes the following actions.
                  > > > dev->process();
                  > > > fb1->process();
                  > > > fb2->process();
                  > > > xmas->process();
                  > > Sounds great (I do like the idea) until we realise it's a REAL
                  > TIME system
                  > > we are working toward.
                  > >
                  > > So lets plug some (Made UP) figures into this system and apply some
                  > > restrictions and assumptions to the system.
                  > >
                  > > Assumptions
                  > > ALL inputs and outputs aren't buffered and can only hold 1
                  > byte of data at
                  > > a time.
                  > > TI = Time Interval
                  > >
                  > > Timings (No basis in reality just for demonstration)
                  > > DEV
                  > > Input arrives every 1 TI
                  > > stay valid for .5 TI
                  > > Process takes .5 TI
                  > >
                  > > FD1/2
                  > > Process takes .5 TI
                  > >
                  > > xmas
                  > > Process takes .5 TI
                  >
                  > If the processing for every sample takes longer than the interval
                  > between samples, then we are stuffed in any case -- even if we had a
                  > different networking model, or huge buffers, the processing would just
                  > get farther and farther behind the input.
                  >
                  > So, in your model, the total processing must be less than 1 TI,
                  > whichever way we arrange the networking code. If it doesn't, then
                  > your computer simply isn't fast enough to do what you want to do.
                  >
                  > The only way around this is to do what you do when you are handing
                  > audio, and that is to optimise the processing code by breaking up the
                  > audio into 64-sample (or larger) chunks, which are faster to process
                  > and pass around. However, in our situation, dealing with data at
                  > 256Hz, say, working in 64-sample chunks results in a 250ms delay.
                  >
                  > For the kind of data rates we're using (e.g. 256Hz, rather than audio
                  > rates of 44100Hz), I think processing one sample at a time would be
                  > quite feasible. Working in chunks of 4 or 8 samples might also be
                  > do-able, which could give a small increase in speed, but I don't think
                  > it is worth the extra coding complexity and signal delays. Also, it
                  > really would start getting messy if we tried to handle signals with
                  > different sampling rates in 4-sample chunks (e.g. 16Hz and 256Hz).
                  >
                  > As a guide to the processing power required, imagine what kind of spec
                  > machine you would need to run a network in one of those audio plugin
                  > platforms like Buzz or Cubase, and then remember that we're dealing
                  > with data at roughly 1/100th of the sampling rate. So we don't need
                  > *that* powerful a machine to do what we want to do.
                  >
                  > I hope this helps --
                  >
                  > Jim
                  >
                  > --
                  > Jim Peters (_)/=\~/_(_) jim@...
                  > (_) /=\ ~/_ (_)
                  > Uazú (_) /=\ ~/_ (_) http://
                  > B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
                  >
                  >
                  > To unsubscribe from this group, send an email to:
                  > buildcheapeeg-unsubscribe@egroups.com
                  >
                  >
                  >
                  > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
                  >
                  >
                  >
                • Jim Peters
                  ... Yes, it will wrap all by itself (using the ++ operator), so we don t need to worry about this so long as we are only doing straight == or != comparisons.
                  Message 8 of 13 , Apr 2, 2002
                  • 0 Attachment
                    Dave wrote:
                    > And then just have this value wrap back to zero when the integer
                    > maxes out (INT_MAX, or UINT_MAX if unsigned)?

                    Yes, it will wrap all by itself (using the ++ operator), so we don't
                    need to worry about this so long as we are only doing straight == or
                    != comparisons.


                    > I am a bit concerned about doing this unbuffered, and would want to
                    > throw together some tests to see what happens when we scale it
                    > upwards by adding more and more process() calls. As long as the
                    > combined process() calls are faster than the rate at which data is
                    > streaming, all would be fine. I suppose that would hold true for
                    > any amount of processing we did, so buffered or unbuffered, we are
                    > going to have to handle the data faster than it comes in. I dunno;
                    > it will take a few tests to find out if this is an issue or not.

                    The only problem I can see is if people decide they want to do a big
                    FFT every 16 samples, say, which could mess up the whole thing because
                    a big FFT might take more than the time available within one sample
                    period. Slower operations like this could be moved over into another
                    Network in a lower priority thread (see ideas of a Bridge lower down).


                    > What I think you have, then, is a variation on the MVC paradigm. In
                    > this case, the "model" is your Node-supervisory code which knows
                    > about the data and all the "views" attached to the data. The
                    > attached observer views and their update() calls would be akin to
                    > your linked Nodes with their process() calls. However, MVC uses a
                    > notification system to the views, telling them when new data is
                    > available. And, as I understand it, it is up to each view to then
                    > to call the model to actually get the updated data. This is
                    > different from your idea where the model (i.e., node-supervisor)
                    > would be respondible for calling the update() views directly.

                    I guess it is all the same, one way or another.


                    > I don't know.... because if we say that, then the definition of a
                    > Sensor changes in that a sensor object now also takes on the meaning
                    > and function that is in the Device class. Perhaps it is more
                    > accurate to say that any object which produces or receives real time
                    > sample data inherits the Node class. Thus, the BioDevice class
                    > would inherit Node. It would be up to BioDevice to add the correct
                    > number of out[nn] data streams.

                    Okay, fine. I think we have two choices -- either you inherit from
                    Node, or you create a helper class which inherits from 'Node' that you
                    then embed in your class instance. For example, I'm thinking about a
                    'bridge' that has two Nodes, one in each of two different networks
                    (probably in two different threads) that allows data streams to pass
                    between different threads via a bunch of circular buffers. Obviously
                    this can't inherit from Node twice (at least, not so far as I know in
                    C++), so I think I'll need two helper classes, with instances of these
                    classes embedded in the 'bridge' class.


                    > I think that the above should not be a "Sensor," but instead
                    > "Device" -- or more pointedly, BioDevice. This might simply be a
                    > difference in the use in terminology, but I think it is important to
                    > clear up. The physical correlate of a BioSensor is an
                    > electrode/wire. Thus, a BioDevice will have one more more
                    > BioSensors. When you say above that "a Sensor is generating two
                    > channels of data," I think that shoud really read as "a BioDevice is
                    > generating two channels of data." This makes a difference in the
                    > way we use our BioDevice and BioSensor objects internally. It also
                    > helps keep behavior and function separate based on what we want to
                    > interact with -- a BioDevice or a BioSensor.

                    Okay, fine. A "BioDevice" typically has a whole bunch of
                    "BioSensors", then.

                    > What I like about your plan is the patch-chord kind of arrangment of
                    > the objects, where you can daisy-chain input and outputs together in
                    > a variety of configurations. This could keep data flows very
                    > flexible based on what may be needed later on down the line in terms
                    > of biofeedback protocols.

                    I think this is what everyone has been asking for all this time.


                    > Ok... except dev, fb1, fb2, and xmas would really be pointers kept
                    > in a list which would then be controlled by the node-supervisory
                    > code, right? The more I think about this, the more it seems like
                    > there should be a Network class to handle traversal of the nodes as
                    > well as adding or removing nodes from the list

                    Yes, that is a good idea, and I'm working with that idea now.


                    > What I would like to see is it more situated within the
                    > BioDevice/BioSensor framework. This would alleviate the need for
                    > node-supervisory code being in the node code (as globals or
                    > whatever), and keep the flow more natural in terms of the system.

                    I'm working on a test implementation now that doesn't use globals --
                    instead every Node belongs to a Network. That means we can have
                    several Networks running in different threads, or even in the same
                    thread. Even if we don't actually need multiple Networks, it is a
                    cleaner way to do it.


                    > For example, we've already touched on the issue of what kicks the
                    > whole network into motion. The natural starting place for that
                    > kick-off would be when data is received from a sensor. This is
                    > controlled by the BioDevice object, which reads the raw data stream
                    > in from the port/device and is able to separate it out into
                    > individual sensor streams for our use (or, plug one byte at a time
                    > into a receiving node as per your plan -- I am using the word
                    > "stream" here loosely). Otherwise, where (or who) would start the
                    > traversal of the node/port tree? If I am understanding correctly,
                    > that traversal will only occur when there is data ready from the
                    > external device for a particular port in the node list. Are there
                    > are other situations I'm not thinking of?

                    The only possibility is if there is more than one input stream we're
                    feeding into the network through different Nodes. Anyway, I'm going
                    with your idea of letting the BioDevice code control the network (or
                    at least have some 'main loop' alternate between calling the BioDevice
                    and running the network of nodes). As you say, this is all flexible
                    enough that we can add to and improve this later if necessary.


                    > If we do need to add some synchronization mechanisms, things like
                    > semaphores offer low overhead for this.

                    I think that if we are using a Network class to maintain the Nodes,
                    then we don't need the globals, and we can also do without semaphores
                    by using circular lock-free buffers for passing data between threads.
                    (I've used these before).


                    > Based on prior discussions, it seemed like others were not in favor
                    > of building in support for multiple devices, thus I am not sure
                    > under what conditions there would be a reason to have more than one
                    > producer node in the network. I would not mind having the
                    > flexibility of adding such capability, but am thinking that this
                    > will effect the answer to the question of who kicks off the
                    > traversal of the network when new data arrives.

                    I was thinking of work I did previously where I was handling a general
                    message-passing network, where messages might arrive from all kinds of
                    places. This required message generator 'nodes' to register the
                    filehandles they were waiting on with supervisor code which did the
                    select() call for all of them at once. We probably don't need
                    anything this complex, though, right ?

                    Actually, it was not only generator nodes that required select()
                    support, but also nodes that were waiting to write on blocking output
                    streams. Hopefully if we allow generous buffers between threads, the
                    buffers will only overflow in true processor-overload situations.


                    > Right now the way I see it is that the whole process will block
                    > until data is received from the external device (in BioDevice). I
                    > can see that there would be ways to extend this design later on if I
                    > or someone else really wants multiple device support.

                    Agreed.

                    As I've mentioned, I'm working on a test implementation of this. I'm
                    coding in simple C++, and using C for strings and so on.

                    The basic structure is there, but I've been trying to think of ways to
                    optimise it even further. However, I haven't found anything as
                    flexible and simple as what I've already suggested. With more
                    information provided by individual Nodes, certain other optimisations
                    could be made, but only at the expense of additional complexity for
                    both Node-writers and the Node/Network classes. So I'm sticking with
                    the simpler implementation.

                    The whole idea is to make something fairly robust, efficient and
                    flexible so that we can just forget about it and get on with using it
                    to build more interesting things.

                    Jim

                    --
                    Jim Peters (_)/=\~/_(_) jim@...
                    (_) /=\ ~/_ (_)
                    Uazú (_) /=\ ~/_ (_) http://
                    B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
                  • John Morrison
                    Message 9 of 13 , Apr 2, 2002
                    • 0 Attachment
                      <<<< This was written today before Jim Posted his reply but I didn't want to
                      wast all that typing >>>>
                      <<<< Wrote this on my 2 hours train travel to work.......I love my Laptop
                      :-) >>>>

                      Been having a little thinking over the Easter break and thought I’d run this
                      hybrid idea (based on Jims original idea) past the general population.

                      Assumptions/Constraints
                      First thing Context switching is a pain and chews up processing time but in
                      some cases is required. :-(

                      The original “1 thread” proposed has the major disadvantage that if any
                      component gets into an endless loop or in some way locks up whole program
                      stops. So I think we should have a thread for the user interaction so that
                      if something does lockup at least the user can click “Exit”. Also there
                      WILL be ”User interface” modules that require constant updates even when
                      there is no real data. Eg MP3 player, animations, Setting up and closing
                      down the network.

                      On the other end of things I’m concerned about the I/O being lumped in with
                      the processing and the possibility of loosing data (How long does a byte
                      stay valid from an i/o device?). So I think that a thread should be
                      allocated to the “Device” section.

                      Network of Nodes
                      I’m a little worried about buffering only 1 character/block at a time it
                      was perfectly fine with just one thread BUT as I’ve said above we “may”
                      loose data and have lockups you can’t escape from. So I propose a circular
                      buffer with the size specified by the next stage(s) this also gives us a
                      rewind capability for the next stage without instituting new code.


                      Proposal
                      3 threads
                      - Device
                      - Processing
                      - User interaction
                      Each of these threads would be handled by the “network of nodes” system.

                      Node Class
                      Each node within the system has to contain a “Node” object that is used as
                      the interface between modules.

                      ModuleA -> Node1 ---> ModuleB -----> Node2---> ModuleC -> Node3
                      \-----(Node 1 to
                      ModuleC)----/

                      Setup (for above network)
                      Instantiate ModuleA
                      Instantiate ModuleB
                      Instantiate ModuleC
                      Instantiate Node1
                      Instantiate Node2
                      Instantiate Node3

                      ModuleA.outputNode(referance to Node1)
                      ModuleB.outputNode(referance to Node2)
                      ModuleC.outputNode(referance to Node3)

                      ModuleB.addInputNode(referance to Node1)
                      ModuleC.addInputNode(referance to Node1)
                      ModuleC.addInputNode(referance to Node2)

                      Operation by networkMain object(for above network)
                      // Check if new data exists
                      If Node1.newData()
                      Node1.resetDataFlag() (Is set when new data written)
                      ModuleA.process()
                      ModuleB.process()
                      ModuleC.process()
                      (Must be done after ModuleB has finished)

                      Contents of Process
                      FOR EACH node in InputVector
                      If Node.newData()
                      Node.getElement(CurrentCount_ForThisNode);
                      //
                      // Do some processing //
                      //
                      CurrentCount = (CurrentCount+1) % MaxCount


                      Each Node is fully controlled by the modules connected to it
                      (NO autonomous action).
                      Each Node represents 1 stream of data.
                      Each Node has only 1 input Module but can have more than one output
                      Module(eg node1 above).
                      Scanning is only done on the first node in any path, which allows for
                      multiple threads.
                      There is no need for a source module to keep track of destination nodes,
                      as the destination will collect data.
                      Temporary bottlenecks handled with ease by buffers.

                      Anyway that it’s for now I’ve got lots more to go but no time.
                      Any suggestions on weather this will or won’t work???


                      John
                    • Dave
                      ... ... That s an interesting solution, having two networks and bridge nodes between them. What is going to get tricky is patch-chording between the
                      Message 10 of 13 , Apr 2, 2002
                      • 0 Attachment
                        On Tue, 2 Apr 2002 11:17:40 +0100, Jim Peters wrote:

                        >The only problem I can see is if people decide they want to do a big
                        >FFT every 16 samples, say, which could mess up the whole thing because
                        >a big FFT might take more than the time available within one sample
                        >period. Slower operations like this could be moved over into another
                        >Network in a lower priority thread (see ideas of a Bridge lower down).

                        <snip>

                        >Okay, fine. I think we have two choices -- either you inherit from
                        >Node, or you create a helper class which inherits from 'Node' that you
                        >then embed in your class instance. For example, I'm thinking about a
                        >'bridge' that has two Nodes, one in each of two different networks
                        >(probably in two different threads) that allows data streams to pass
                        >between different threads via a bunch of circular buffers. Obviously
                        >this can't inherit from Node twice (at least, not so far as I know in
                        >C++), so I think I'll need two helper classes, with instances of these
                        >classes embedded in the 'bridge' class.

                        That's an interesting solution, having two networks and bridge nodes between
                        them. What is going to get tricky is "patch-chording" between the networks.
                        You would not be able to have any nodes in NetworkA (the fast network) be
                        dependent on the output from anything in NetworkB (the slow network). Plus,
                        from an OO/application standpoint, we now need something which can manage all
                        the networks. This could get complicated. John's post has me thinking that
                        perhaps it would simplify things to keep data acquisition and data processing
                        in two separate threads, rather than try to separate slow process()'s out
                        piecemeal. It might make the whole system more managable?

                        >> Ok... except dev, fb1, fb2, and xmas would really be pointers kept
                        >> in a list which would then be controlled by the node-supervisory
                        >> code, right? The more I think about this, the more it seems like
                        >> there should be a Network class to handle traversal of the nodes as
                        >> well as adding or removing nodes from the list
                        >
                        >Yes, that is a good idea, and I'm working with that idea now.

                        Ironically, I implemented your idea using the embedded 'static' code in each
                        Node. I have stubbed out code for a BioNodeNetwork class, and then decided to
                        move those methods into the Node class. Either way work, and each has its
                        attractions for me. I really like being able to simply declare a Node anywhere
                        in the program, and having it automatically become a part of the node network.
                        The code does not need to know anything about a global reference to a
                        particular NodeNetwork object, just whatever nodes it wants to connect to,
                        which it can query from "itself" once it is in the network. Kind of
                        fractal-like, where the whole is encoded in the part.

                        But I think it would be worthwhile to go back to my feelings of separating it
                        out to a NodeNetwork after all, because you bring up some good points about
                        being able to create other Networks for other purposes, not simply for multiple
                        device interfaces.

                        >> What I would like to see is it more situated within the
                        >> BioDevice/BioSensor framework. This would alleviate the need for
                        >> node-supervisory code being in the node code (as globals or
                        >> whatever), and keep the flow more natural in terms of the system.
                        >
                        >I'm working on a test implementation now that doesn't use globals --
                        >instead every Node belongs to a Network. That means we can have
                        >several Networks running in different threads, or even in the same
                        >thread. Even if we don't actually need multiple Networks, it is a
                        >cleaner way to do it.

                        That's what I was thinking originally. I had never instantiated several
                        objects with shared memory, though (via static data and methods) and got
                        fascinated with it. :-) So it was a cool diversion and interesting for
                        experience, but having multiple Networks, and separating the managerial code
                        from the nodes themselves makes more OO sense, I think.

                        >> traversal of the node/port tree? If I am understanding correctly,
                        >> that traversal will only occur when there is data ready from the
                        >> external device for a particular port in the node list. Are there
                        >> are other situations I'm not thinking of?
                        >
                        >The only possibility is if there is more than one input stream we're
                        >feeding into the network through different Nodes. Anyway, I'm going
                        >with your idea of letting the BioDevice code control the network (or
                        >at least have some 'main loop' alternate between calling the BioDevice
                        >and running the network of nodes). As you say, this is all flexible
                        >enough that we can add to and improve this later if necessary.

                        For now, it works well there, and it makes sense to kick off the network once
                        data is received from an external source. Handling multiple input streams into
                        one Network would mean reorganizing the objects to some extent. I think it
                        would mean going to some kind of DeviceManager that could monitor incoming data
                        and fire off the Network. This would avoid having two BioDevices (or some
                        other source) in separate threads firing off the Network simultaneously.
                        Either that, or using synchronization techniques in the Network class itself to
                        kick it into motion.

                        Right now I have the Network kicked into motion in biodeviceprocompserial.cpp
                        as follows:

                        //
                        // We have inserted new values in some sensor Out Ports. Traverse
                        // the node network to update any other nodes who are watching
                        // those Out Ports.
                        //

                        BioNode::ProcessNodeNetwork();

                        This makes a call to the *class* wide method (cool :). But as I mentioned last
                        night, I have a lot more testing to do to see how it bears up under a
                        processing load. To change it in the way we are talking about above, I guess I
                        would have to pass the BioNodeNetwork object into BioDevice when the BioDevice
                        object is created. I don't think I want BioDevice to inherit BioNodeNetwork,
                        because other objects are going to need access to the BioNodeNetwork object.
                        Does this mean that the instantiated Network object is going to need to be
                        global? Or should it be a part of BioDevice itself? The latter only makes
                        sense if we are committed to there being only one input source per network.
                        But if not, then a Network is more autonomous...

                        >> If we do need to add some synchronization mechanisms, things like
                        >> semaphores offer low overhead for this.
                        >
                        >I think that if we are using a Network class to maintain the Nodes,
                        >then we don't need the globals, and we can also do without semaphores
                        >by using circular lock-free buffers for passing data between threads.
                        >(I've used these before).

                        Could you explain a little bit more of what you mean by circular lock-free
                        buffers? Do you mean having something like a two-way pipe stream between the
                        threads?

                        >> Based on prior discussions, it seemed like others were not in favor
                        >> of building in support for multiple devices, thus I am not sure
                        >> under what conditions there would be a reason to have more than one
                        >> producer node in the network. I would not mind having the
                        >> flexibility of adding such capability, but am thinking that this
                        >> will effect the answer to the question of who kicks off the
                        >> traversal of the network when new data arrives.
                        >
                        >I was thinking of work I did previously where I was handling a general
                        >message-passing network, where messages might arrive from all kinds of
                        >places. This required message generator 'nodes' to register the
                        >filehandles they were waiting on with supervisor code which did the
                        >select() call for all of them at once. We probably don't need
                        >anything this complex, though, right ?

                        I think that would only be necessary if we had multiple input sources, such as
                        your above network, which could receive messages from many different sources.
                        But I *think* that having multiple input sources for this project would be more
                        rare, and that it will mostly be one source per Network. Thus, I am thinking
                        that should there be an interest in having multiple input sources, that perhaps
                        a merger Network could be implemented. Perhaps something like this:

                        | BioDeviceNetworkA |
                        | BioDeviceNetworkB |
                        ================
                        |
                        |
                        v
                        BioDataNetwork

                        NetworkA and NetworkB could have one set of nodes for their output. Their
                        process() method could simply trigger an event in BioDataNetwork which wakes it
                        up to then process its network. I dunno... it is certainly more
                        straightforward to have one input source per Network, but I like to keep my
                        options open, too, for future needs.

                        >Actually, it was not only generator nodes that required select()
                        >support, but also nodes that were waiting to write on blocking output
                        >streams. Hopefully if we allow generous buffers between threads, the
                        >buffers will only overflow in true processor-overload situations.

                        That, or make them non-blocking if we don't want to hang up our network waiting
                        on a write(). I think we will get into some portability issues with that,
                        though.

                        >As I've mentioned, I'm working on a test implementation of this. I'm
                        >coding in simple C++, and using C for strings and so on.

                        That's great. I had a feeling that you might be doing something like this
                        also. It will be great to compare notes.

                        >The basic structure is there, but I've been trying to think of ways to
                        >optimise it even further. However, I haven't found anything as
                        >flexible and simple as what I've already suggested. With more
                        >information provided by individual Nodes, certain other optimisations
                        >could be made, but only at the expense of additional complexity for
                        >both Node-writers and the Node/Network classes. So I'm sticking with
                        >the simpler implementation.

                        That sounds good. What I've got right now is the bare bones of what we've
                        talked about, with the addition of some descriptive strings for each
                        node/network.

                        >The whole idea is to make something fairly robust, efficient and
                        >flexible so that we can just forget about it and get on with using it
                        >to build more interesting things.

                        That would be *great*. It was very easy to drop in place of what I had done
                        with streams and sockets. Plus, I can bring those streams back if I want to
                        using the process() calls. So, at a lower level, things are much simpler with
                        less overhead. And that's *great*. You've seemed to come up with the best of
                        both worlds. Let's keep working the design and see what we flesh out.

                        Dave.
                      • Dave
                        ... 2 hours?! Wow... that is one long commute. ... I know that Jim-P mentioned that the first conception of a node-network was assuming one thread, but, I
                        Message 11 of 13 , Apr 2, 2002
                        • 0 Attachment
                          On Tue, 2 Apr 2002 23:32:38 +1000, John Morrison wrote:

                          ><<<< This was written today before Jim Posted his reply but I didn't want to
                          >wast all that typing >>>>
                          ><<<< Wrote this on my 2 hours train travel to work.......

                          2 hours?! Wow... that is one long commute.

                          > The original �1 thread� proposed has the major disadvantage that if any
                          >component gets into an endless loop or in some way locks up whole program
                          >stops. So I think we should have a thread for the user interaction so that
                          >if something does lockup at least the user can click �Exit�. Also there
                          >WILL be �User interface� modules that require constant updates even when
                          >there is no real data. Eg MP3 player, animations, Setting up and closing
                          >down the network.

                          I know that Jim-P mentioned that the first conception of a node-network was
                          assuming one thread, but, I think, he meant this relative only for the network
                          -- not for the application as a whole. Thus, the Device would have its own
                          thread, other UI components will have theirs, and so forth, as you mention
                          above.

                          > ModuleA.outputNode(referance to Node1)
                          > ModuleB.outputNode(referance to Node2)
                          > ModuleC.outputNode(referance to Node3)
                          >
                          > ModuleB.addInputNode(referance to Node1)
                          > ModuleC.addInputNode(referance to Node1)
                          > ModuleC.addInputNode(referance to Node2)
                          >
                          > Operation by networkMain object(for above network)
                          > // Check if new data exists
                          > If Node1.newData()
                          > Node1.resetDataFlag() (Is set when new data written)
                          > ModuleA.process()
                          > ModuleB.process()
                          > ModuleC.process()
                          > (Must be done after ModuleB has finished)

                          I'm not sure what object is reading data from the Device in your example above.
                          Perhaps ModuleA? If I am understanding the above correctly, then we still run
                          into the problem of having dependant processing nodes which might take too long
                          before we got back to the next read() on the Device. Meaning that ModuleC
                          could not be called until ModuleB was done, and ModuleB could not be called
                          until ModuleA was done, and so forth. Once Node1.newData senses waiting data
                          from the Device (ModuleA?), then it will start processing the node tree and,
                          when finished with the last Module, finally get back to reading from the
                          Device.

                          Or do you see the Device being in its own separate thread, and feeding data
                          into the node network in some other way? Since you mention that each Node has
                          it's own data stream, then I am thinking that you are envisioning the Device
                          thread and the node-complex thread connected by a buffered stream?

                          Dave.
                        • John Morrison
                          ... Sorry I meant an hour each way........ :-( ... was ... network ... own ... above. OK that puts a different complexion on things. :-) ... above. I ll
                          Message 12 of 13 , Apr 2, 2002
                          • 0 Attachment
                            > ><<<< This was written today before Jim Posted his reply but I
                            > didn't want to
                            > >wast all that typing >>>>
                            > ><<<< Wrote this on my 2 hours train travel to work.......
                            >
                            > 2 hours?! Wow... that is one long commute.
                            Sorry I meant an hour each way........ :-(

                            > > The original “1 thread” proposed has the major disadvantage
                            > that if any
                            > >component gets into an endless loop or in some way locks up whole program
                            > >stops. So I think we should have a thread for the user
                            > interaction so that
                            > >if something does lockup at least the user can click “Exit”. Also there
                            > >WILL be ”User interface” modules that require constant updates even when
                            > >there is no real data. Eg MP3 player, animations, Setting up and closing
                            > >down the network.
                            >
                            > I know that Jim-P mentioned that the first conception of a node-network
                            was
                            > assuming one thread, but, I think, he meant this relative only for the
                            network
                            > -- not for the application as a whole. Thus, the Device would have its
                            own
                            > thread, other UI components will have theirs, and so forth, as you mention
                            above.
                            OK that puts a different complexion on things. :-)


                            > > ModuleA.outputNode(referance to Node1)
                            > > ModuleB.outputNode(referance to Node2)
                            > > ModuleC.outputNode(referance to Node3)
                            > >
                            > > ModuleB.addInputNode(referance to Node1)
                            > > ModuleC.addInputNode(referance to Node1)
                            > > ModuleC.addInputNode(referance to Node2)
                            > >
                            > > Operation by networkMain object(for above network)
                            > > // Check if new data exists
                            > > If Node1.newData()
                            > > Node1.resetDataFlag() (Is set when new data written)
                            > > ModuleA.process()
                            > > ModuleB.process()
                            > > ModuleC.process()
                            > > (Must be done after ModuleB has finished)
                            >
                            > I'm not sure what object is reading data from the Device in your example
                            above.
                            I'll clarify it. :-) SORRY!!!
                            OK think of this as ONLY the processor stage.
                            In this case I should have added a Node0 being the connection to the
                            previous stage.
                            Hows this?
                            Node0 --> ModuleA -> Node1 --> ModuleB --> Node2---> ModuleC -> Node3
                            \-----(Node 1 to ModuleC)----/

                            Operation by networkMain object(for above network)
                            // Check if new data exists for processor stage
                            If Node0.newData()
                            Node0.resetDataFlag() (Is set when new data written to node)
                            ModuleA.process()
                            ModuleB.process()
                            ModuleC.process()



                            > Perhaps ModuleA? If I am understanding the above correctly, then we
                            still run
                            > into the problem of having dependant processing nodes which might take too
                            long
                            > before we got back to the next read() on the Device.
                            Devices are in the previous stage with their own thread and Node0 handles
                            the buffering and any partial delays.
                            Of course if the processing takes longer to process then the data than for
                            ti to arrive will well have to loose data or speed it all up.


                            > Meaning that ModuleC could not be called until ModuleB was done, and
                            ModuleB could not
                            > be called until ModuleA was done, and so forth.
                            YEP!!

                            > Once Node1.newData senses waiting data from the Device (ModuleA?), then it
                            will start processing the
                            > node tree and, when finished with the last Module, finally get back to
                            reading from the
                            > Device.
                            Yep sorry I should have put in Node0.......... :-(

                            > Or do you see the Device being in its own separate thread, and feeding
                            data
                            > into the node network in some other way? Since you mention that each Node
                            has
                            > it's own data stream, then I am thinking that you are envisioning the
                            Device
                            > thread and the node-complex thread connected by a buffered stream?
                            Each node IS a buffer the previous Module places data into it's buffer and
                            the next Module take data from the Node.

                            When you register an output node (method outputNode()) the node ask the
                            module how big a buffer it requires and adjusts accordingly always taking
                            the buffer to the biggest asked for if there are more than 1 output modules.
                            This is the only time that a Node calls a Module ALL other times the
                            Module(s) call the node.

                            > Dave.
                            John
                          • Jim Peters
                            ... Yes -- using a setup like this, it would have to be one-way communication only: from network A (fast) to network B (slow), but not back again. Really this
                            Message 13 of 13 , Apr 3, 2002
                            • 0 Attachment
                              Dave wrote:
                              > That's an interesting solution, having two networks and bridge nodes
                              > between them. What is going to get tricky is "patch-chording"
                              > between the networks. You would not be able to have any nodes in
                              > NetworkA (the fast network) be dependent on the output from anything
                              > in NetworkB (the slow network).

                              Yes -- using a setup like this, it would have to be one-way
                              communication only: from network A (fast) to network B (slow), but not
                              back again. Really this will all be a lot easier to judge when we
                              know the limitations of some of the processing nodes we might want to
                              be running.


                              > This could get complicated. John's post has me thinking that
                              > perhaps it would simplify things to keep data acquisition and data
                              > processing in two separate threads, rather than try to separate slow
                              > process()'s out piecemeal. It might make the whole system more
                              > managable?

                              You might be right there -- put the serial port handler in a
                              high-priority thread by itself so that processing delays won't affect
                              it, and then a big FFT every 16 samples might not be such a big deal.

                              In any case, we have the flexibility to choose either solution closer
                              to the time when we know how this might actually need to work.


                              > To change it in the way we are talking about above, I guess I would
                              > have to pass the BioNodeNetwork object into BioDevice when the
                              > BioDevice object is created.

                              Agreed -- you need to tell it which Network it belongs to.

                              > Does this mean that the instantiated Network object is going to need
                              > to be global? Or should it be a part of BioDevice itself? The
                              > latter only makes sense if we are committed to there being only one
                              > input source per network. But if not, then a Network is more
                              > autonomous...

                              I think whatever code sets up the BioDevice also sets up the rest of
                              the Network. The Network pointer doesn't have to be a global -- it
                              just gets passed to all the Nodes created in that part of the program.
                              After that point, they know which Network they belong to (assuming
                              they stored the pointer somewhere).

                              I think this will become clearer as other parts develop.


                              > Could you explain a little bit more of what you mean by circular
                              > lock-free buffers? Do you mean having something like a two-way pipe
                              > stream between the threads?

                              No, I'm talking about a one-way pipe that is very quick and efficient
                              and doesn't require any form of locking, so neither thread has to wait
                              even for a moment (unless the buffer is full or empty, of course).
                              There might be a complicated name for this kind of thing, but I don't
                              know what it is. Here is a simple example implementation:

                              struct Buffer {
                              int rd; // Offset of read-pointer into buf[]
                              int wr; // Offset of write-pointer into buf[]
                              double buf[256];
                              };

                              void
                              buffer_init(Buffer *bb) {
                              bb->rd= bb->wr= 0;
                              }

                              // Returns 0: no data available, 1: success, data returned in *rvp
                              int
                              buffer_read(Buffer *bb, double *rvp) {
                              if (bb->rd == bb->wr) return 0;
                              *rvp= bb->buf[bb->rd];
                              bb->rd= 255 & (bb->rd+1);
                              return 1;
                              }

                              // Returns 0: can't write, buffer full; 1: success, data written
                              int
                              buffer_write(Buffer *bb, double val) {
                              int new_wr= 255 & (bb->wr+1);
                              if (new_wr == bb->rd) return 0;
                              bb->buf[bb->wr]= val;
                              bb->wr= new_wr;
                              return 1;
                              }

                              One thread calls only buffer_read(), and the other calls only
                              buffer_write(). There are no race conditions because only the first
                              thread updates the ->wr member, and only the second thread updates the
                              ->rd member.

                              This is all based on the assumption that a write on an 'int' memory
                              location is an atomic operation -- i.e. it is not possible for the
                              other thread to read the ->rd or ->wr member and get a scrambled
                              value. I checked one of the POSIX libraries once, and writing an
                              'int' to memory is atomic on every processor in common use today, so
                              this is safe, I believe. I can check again if anyone needs proof.


                              > NetworkA and NetworkB could have one set of nodes for their output.
                              > Their process() method could simply trigger an event in
                              > BioDataNetwork which wakes it up to then process its network. I
                              > dunno... it is certainly more straightforward to have one input
                              > source per Network, but I like to keep my options open, too, for
                              > future needs.

                              Let's just see how it goes.


                              > That, or make them non-blocking if we don't want to hang up our
                              > network waiting on a write(). I think we will get into some
                              > portability issues with that, though.

                              Sorry -- you do need to set them non-blocking in any case. What I
                              mean is that when you've written everything you can to an output
                              stream, and it can't take any more for the moment, then on UNIX you
                              have to use a select() to wait for the output stream to clear a bit
                              before you can write some more. That means that both input and output
                              on UNIX file-descriptor streams requires the use of select(), which
                              means that both input and output nodes need to register their
                              file-descriptors in the kind of system I was talking about. They get
                              notified when there is either new data (input) or new space to write
                              to (output).

                              If output file descriptors can't be set non-blocking, then their
                              output code has to be moved to another thread unless you're willing to
                              have your network stall every time it has to wait for the output
                              stream. Anyway, I think perhaps this is getting a bit ahead of what
                              we're actually discussing.


                              > >As I've mentioned, I'm working on a test implementation of this.
                              > >I'm coding in simple C++, and using C for strings and so on.
                              >
                              > That's great. I had a feeling that you might be doing something
                              > like this also. It will be great to compare notes.

                              Yes, this could be interesting ...

                              Actually, it's good that you're working with it too, because you are
                              bringing in new ideas and approaches that I hadn't thought about.

                              Jim

                              --
                              Jim Peters (_)/=\~/_(_) jim@...
                              (_) /=\ ~/_ (_)
                              Uazú (_) /=\ ~/_ (_) http://
                              B'ham, UK (_) ____ /=\ ____ ~/_ ____ (_) uazu.net
                            Your message has been successfully submitted and would be delivered to recipients shortly.