|
|
Boost : |
From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-03-28 12:28:36
Hi Stjepan,
sorry for the late response, again. It took me some time to write good
answers and to assemble the attached material into (hopefully)
understandable form...
Stjepan Rajko wrote:
[...]
> If I understand you correctly, you are envisioning something that
> makes "the wire" an object in itself - a buffer which can be placed in
> between in and out pins, or something manipulated by an in_out pin.
Well, sort of.
Pins have types.
An unconnected pin may refer to a default object (whose lifetime is
managed by the framework) or render the processing node temporarily
unusable.
Two connected pins refer to the same object (*1).
The link properties finally specify whether the link is /pulling/,
/pushing/, both or /passive/ (my fault: I didn't discuss all pin/link
properties in my previous post, but originally wanted to, so the "see
below" was pointing to nowhere).
(*1) There are exceptions, but let's not discuss them yet.
> Making connections would then, instead of setting up future function
> calls which pass the signal data in arguments, be connecting the
> components to the buffers (through a one-time notification like
> "here's your buffer").
The framework knows nothing about buffers. It only knows types - with or
without pins. Types with pins can be used to instantiate processing
nodes - types without pins can only be used to transport data.
It's particularly useful to use a processing node as data for compound
data structures (e.g. to attach a node that accepts data of arithmetic
type to the x coordinate of a vector with that type as its scalars,
produced by another node).
> Then, executing the network would consist of
> executing each component in the appropriate order. Is this correct?
Basically, if you put data into the network or request data from the
network, the part which needs reevaluation (determined by the link
properties and by what has changed) is evaluated (note that I haven't
discussed tracking changes, yet).
[...]
> As another performance boost, it might be possible to offer "fast"
> versions of the provided components, which would use a boost function
> instead of a boost signal to handle the output. The benefit is
> increased speed, and the drawback is losing all of the benefits of
> Boost.Signals (including connecting multiple sinks to the same source
> directly).
I agree that it should be possible to have links multiple links
associated with one pin.
We shouldn't be too concerned about implementation details like this one
while designing the system.
[...]
>> Further, I think we don't need an overloaded operators interface. Don't
>> get me wrong, I'm not the "oh no - not so much tricky template stuff"
>> kind of guy (in fact, I like template hacking a lot), but I believe the
>> power of this thing lies in the runtime world.
>
> I like the operator interface because you can connect objects (or
> change / append the network) using something that almost looks like a
> diagram. But that's just my preference :-)
Yes, but I wouldn't make it a top priority, because a clean runtime
interface allows for writing a GUI that lets us draw (and run) real
diagrams ;-).
>> Serialization and a careful implementation that allows to extend things
>> at runtime by loading shared object files is much more important, than
>> fancy compile time setup, IMO. So is multi-threading - ideally the
>> framework is thread-aware and self-optimizing.
>
> What do you mean by serialization?
Storing and loading a network setup from a stream.
Maybe Boost.Serialization can be used, but I'm not sure about that
because it would have to cooperate with the custom memory manager.
Also note that there are ideally two library interfaces; one for running
networks and another one to create and edit them. No code and data of
the latter needs to be compiled in if only the former is needed. The
former only needs a loader, the latter needs serialization in both
directions.
While we're at it: Meta information, that is supposed to mean
information that describes the compile time properties of types, nodes
and pins in the runtime world, can be stored statically and should only
be needed for editing.
> Yes, thread-aware is very
> important. Self-optimizing sounds great but I'm not sure what all
> exactly it can mean and in what all ways it could be tackled.
Yes, that sentence wasn't too precise.
> I think
> as we extend the library towards multi-threading I'll be more aware of
> what the possible optimizations are.
It was supposed to mean: Ideally, the framework would automatically
minimize locking, based on the information which thread executes which
part of the network.
>> Also note that I'm not only talking about a signal processing framework
>> but something more general (signal processing gives an interesting use
>> case, though). One could also use it to wire up the data flow in a batch
>> system, resolve GUI dependencies, create vector graphics or use it as a
>> general purpose programming system.
>>
>> As you can see, I'm potentially interested in collaborating on this
>> project, if I haven't scared you off already ;-).
>
> I do think we are definitelly looking at the same sort of beast :-)
> Also, I'd be keen to collaborate.
Great!
> I'm going to try to sumbit this as
> a SoC proposal, and if it gets accepted I think I'll have to be
> careful to delineate what constitutes the project that I am to
> complete from things to collaborate on.
Sure. What I propose might be too much for an SoC project.
> Have you given the current version of the library a try?
Maybe not. I downloaded the archive shortly after your initial post.
> If you find
> that there is a way in which it lets you do the things you are
> interested in (or something similar), we can use it as a starting
> point. Otherwise, we can try to rethink the design. If you have any
> of the code you've been working on available, I'd be happy to try it
> out and do the same.
Well, most of what I have so far is "pen and paper stuff".
I outlined the basics in a text file attached to this post. Further,
I'll attach an incomplete draft implementation for an evaluator core
(and hope all that stuff won't make the Boost list filter this post).
I also have some "clean and working" code that we could use to manage
generic meta information (as defined above), originally written for
another (non-Boost, so far - slightly related) project of mine.
I hope the material provided works for you to get a relatively clear
picture what I have in mind. I'm curiously looking forward to your response!
Regards,
Tobias
Link properties:
================
Propagation mode:
-----------------
Two flags, "pushing" and "pulling" determine the propagation mode of a link.
Combination | Symbol
------------|--------
passive | ---
pushing | -->
pulling | >--
push&pull | >->
Examples:
a) Pushing links
N1 --> N2 --> N3 --> N4
Pushing to N1:
N1 evaluates, notifies N2
N2 evaluates, notifies N3
N3 evaluates, notifies N4
N4 evaluates
b) Pulling links
N1 >-- N2 >-- N3 >-- N4
Pulling from N4:
N4 requests data from N3
N3 requests data from N2
N2 requests data from N1
N1 evaluates
N2 evaluates
N3 evaluates
N4 evaluates
c) Passive links
N1 --- N --> N4
N2 --> 3
Pushing data to N1:
N1 evaluates
Pushing data to N2:
N2 evaluates, notifies N3
N3 evaluates, notifies N4
N4 evaluates
d) Decoupled Pushing and Pulling
N1 --> N --- N4 >-- N5
N2 --> 3
Pushing data to N1:
N1 evaluates, notifies N3
N3 evaluates
Pushing data to N2:
N2 evaluates, notifies N3
N3 evaluates
Pulling data from N5:
N5 requests data from N4
N4 evaluates
N5 evaluates
e) Mixed pushing and pulling
N1 --> N
N2 >-- 3
Pushing data to N1:
N1 evaluates, notifies N3
N3 requests data from N2
N2 evaluates
N3 evaluates
Pulling data from N3:
N3 requests data from N2
N2 evaluates
N3 evaluates
f) Pushing and Pulling links
N1 >-> N
N2 >-> 3
Pushing data to N1:
N1 evaluates, notifies N3
N3 requests data from N2
N2 evaluates
N3 evaluates
Pushing data to N2:
N2 evaluates, notifies N3
N3 requests data from N1
N1 evaluates
N3 evaluates
Update tracking:
----------------
Update tracking allows the framework to skip evaluation, if it can be
foreseen that there won't be a new result.
- none // updating is not tracked
- ignore // updating is not tracked, always treated as unchanged
- flagged // a flag is raised on update
- watched // the new content is compared against a copy
Examples (a 't' character denotes links with update tracking):
a) Pushing links:
t
N1 --> N2
Pushing data to N1:
N1 evaluates
N2 is notified iff the data has really changed
N2 evaluates eventually
b) Pulling links:
t
N1 >-- N2
Pulling data from N2:
N2 requests data from N1
N1 evaluates
N2 evaluates iff the data from N1 has really changed
c) Passive links:
t
N1 --- N
N2 --> 3
t
Pushing data to N1:
N1 evaluates
Pushind data to N2:
N2 evaluates
N3 is notified, unless the data associated with both inputs is unchanged
d) Decoupled pushing and pulling:
t
N1 --> N --- N4 >-- N5
N2 --> 3
Pushing data to N1:
N1 evaluates, notifies N3
N3 evaluates
Pushing data to N2:
N2 evaluates, notifies N3
N3 evaluates
Pulling data from N5:
N5 requests data from N4
N4 evaluates iff the data from N3 has changed
N5 evaluates iff N4 has been evaluated
e) Mixed pushing and pulling
t
N1 --> N
N2 >-- 3
t
Pushing data to N1:
N1 evaluates, notifies N3
N3 requests data from N2
N2 evaluates
N3 evaluates, unless incoming data is unchanged
Pulling data from N3:
N3 requests data from N2
N2 evaluates
N3 evaluates, unless incoming data from N2 is unchanged
(Note: no need to check the link from N1, in this case. N1 would have
notified us).
Pin properties:
===============
Direction:
----------
- in
- out
- io (basically a shortcut for two, memory constraint pins)
Trigger mode:
-------------
- automatic
The framework does it.
Examples:
a)
N1 --> N2
Pushing data to N1:
N1 evaluates, notifies N2
N2 evaluates
b)
N1 >-- N2
Pulling data from N2:
N2 requests data from N2,
N1 evaluates
N2 evaluates
- on_demand
Only evaluates connected nodes, if the pin has been touched during evaluation.
Update is performed once per evaluation.
Examples:
a)
N1 --> N2
Pushing data to N1:
N1 evaluates
N1 notifies N2 iff data has been written to the link
N2 evaluates, eventually
(Implementation note: This mechanism can reuse the facility for
flagged update tracking)
b)
N1 >-- N2
Pulling data from N2:
N2 evaluates
N2 requests data from N1 on first read from the link
N1 evaluates, eventually
- on_access
Every access of a pin during evaluation causes the network to be evaluated.
Examples:
a)
N1 --> N2
Pushing data to N1:
N1 evaluates
During evaluation of N1, data is pushed to N2 on every write to the link
b)
N1 >-- N2
Pulling data from N2:
N2 evaluates
During evaluation of N2, data is pulled from N1 on every read from the link
- none
Connected links must be passive.
Memory management:
------------------
- maps_to(location, offset = 0)
This property maps a pin to a certain memory address or another pin.
Example:
class vector : public processing_node<vector>
{
float[2] arr_body;
io_pin<float> pin_x, pin_y;
public:
vector()
: arr_body()
, pin_x("x",maps_to(arr_body,0))
, pin_y("y",maps_to(arr_body,1))
{ }
// [...]
};
- allow_inplace_processing(other_pin)
Tells the framework that it's legal to map the pins to the same address.
The framework may or may not do anything based on this information - this
property is a hint for automatic optimization.
Generic types
=============
Special, generic types allow pins to accept arbitrarily typed data.
Example:
// 2:1 Multiplexer
class mux_2_1 : processing_node<mux_2_1>
{
input_pin<int> pin_select;
input_pin<generic1, trigger<on_access>, restrict_to<pulling> > pin_input0
input_pin<generic1, trigger<on_access>, restrict_to<pulling> > pin_input1;
output_pin<generic1, restrict_to<pulling> > pin_output;
public:
// [...]
void evaluate()
{
pin_output = !pin_select ? pin_input0 : pin_input1;
}
};
// Sidenote:
//
// this implementation only does proper lazy evaluation in pulling context:
//
// IN0 >-- M
// SEL --- U >-- OUT
// IN1 >-- X
//
// To make it work with a pushing evaluation scheme
//
// IN0 --> M
// SEL --- U --> OUT
// IN1 --> X
//
// we'll rewrite the code as follows:
class mux_2_1 : processing_node<mux_2_1>
{
input_pin<int> pin_select;
input_pin<generic1, trigger<on_demand> > pin_input0
input_pin<generic1, trigger<on_demand> > pin_input1;
output_pin<generic1, trigger<on_demand> > pin_output;
public:
// [...]
void evaluate()
{
if (! pin_select)
{
if (pin_input0.touched())
pin_output = pin_input0;
}
else
{
if (pin_input1.touched())
pin_output = pin_input1;
}
pin_input0.untouch();
pin_input1.untouch();
}
};
Dynamic pins:
=============
Attaching pins to processing nodes at runtime to implment e.g. an
N:1 multiplexer.
TODO: details
Abstract processing nodes:
==========================
Allow the implementation of a processing node to vary based on the data
types of its links.
TODO: details
Capsules:
=========
Use a network as a new processing node. Pins can be exposed to the client
selectively.
TODO: details
#include <list>
// signal propagation / incomplete toy draft for the evaluation core
namespace my
{
class pin; class node;
// "everyone's friend" to hide framework stuff from the user
class framework_access
{
public:
static int * & data_pointer(pin & that);
static void add_pre_eval_peer(node & n, node * p);
static void add_post_eval_peer(node & n, node * p);
};
// the simplest form of a pin just holds a pointer to the data
class pin
{
friend class framework_access;
int * ptr_data;
public:
pin() : ptr_data(0l) { }
explicit pin(int * data) : ptr_data(data) { }
int & operator*() const { return *this->ptr_data; }
};
// the node base class manages the links
class node
{
friend class framework_access;
// links to nodes with inputs pulling from
std::list<node*> seq_pre_eval;
// links to nodes with outputs pushing to
std::list<node*> seq_post_eval;
typedef std::list<node*>::iterator node_list_iterator;
protected:
// prevent accidental copy
node()
: seq_pre_eval(), seq_post_eval()
{ }
node(const node & that)
: seq_pre_eval(that.seq_pre_eval), seq_post_eval(that.seq_post_eval)
{ }
// polymorphic interface
// implemented with virtual functions - maybe just for now
virtual void evaluate() = 0;
public:
virtual void update(node * /* sender */)
{
// unused sender parameter is needed once we support links
// that can be both pulling and pushing at the same time to
// avoid endless recursion
for(node_list_iterator i = seq_pre_eval.begin(),
e = seq_pre_eval.end(); i != e; ++i) (*i)->update(this);
evaluate();
for(node_list_iterator i = seq_post_eval.begin(),
e = seq_post_eval.end(); i != e; ++i) (*i)->update(this);
}
virtual ~node()
{ }
};
// grant access to link sequences
int * & framework_access::data_pointer(pin & that)
{
return that.ptr_data;
}
void framework_access::add_pre_eval_peer(node & n, node * p)
{
n.seq_pre_eval.push_back(p); // hacky
}
void framework_access::add_post_eval_peer(node & n, node * p)
{
n.seq_post_eval.push_back(p); // hacky
}
// functions to set up links
// actually we should avoid duplicate entries - but not for now
void connect_pushing(node * out_pin_owner, pin & out_pin,
node * in_pin_owner, pin & in_pin)
{
// get memory - we'll just pretend we got some, for now
static int buf;
// map data pointers to the same address
framework_access::data_pointer(in_pin) = & buf;
framework_access::data_pointer(out_pin) = & buf;
// set up notification
framework_access::add_post_eval_peer(*out_pin_owner,in_pin_owner);
}
void connect_pulling(node * out_pin_owner, pin & out_pin,
node * in_pin_owner, pin & in_pin)
{
// get memory - we'll just pretend we got some, for now
static int buf;
// map data pointers to the same address
framework_access::data_pointer(in_pin) = & buf;
framework_access::data_pointer(out_pin) = & buf;
// set up notification
framework_access::add_pre_eval_peer(*in_pin_owner,out_pin_owner);
}
}
#include <cstdlib>
#include <iostream>
struct foo_node : my::node
{
my::pin pin_out;
virtual void evaluate()
{
*pin_out = std::rand();
std::cout << "foo_node: producing value " << *pin_out << std::endl;
}
};
struct bar_node : my::node
{
my::pin pin_in;
virtual void evaluate()
{
std::cout << "bar_node: received value " << *pin_in << std::endl;
}
};
int main()
{
foo_node a_foo_node, another_foo_node;
bar_node a_bar_node, another_bar_node;
my::connect_pushing(& a_foo_node, a_foo_node.pin_out,
& a_bar_node, a_bar_node.pin_in);
my::connect_pulling(& another_foo_node, another_foo_node.pin_out,
& another_bar_node, another_bar_node.pin_in);
std::cout << "foo --> bar" << std::endl << "===========" << std::endl;
std::cout << "main: updating foo" << std::endl;
a_foo_node.update(0l);
std::cout << "main: updating bar" << std::endl;
a_bar_node.update(0l);
std::cout << std::endl;
std::cout << "foo >-- bar" << std::endl << "===========" << std::endl;
std::cout << "main: updating foo" << std::endl;
another_foo_node.update(0l);
std::cout << "main: updating bar" << std::endl;
another_bar_node.update(0l);
std::cout << std::endl;
return 0;
}
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk