Three months since the last post? Where are you? Is YetiSim dead, or just one of those projects that starts but never goes anywhere? Well the short answer is, I’ve taken a strategic retreat to really update my skills to make YetiSim even cooler. Now with some updated C++ and parallel skills, it’s time to get down to making YetiSim super cool.
Today was my last day at Spring Sim. I attended most of a talk in the morning, which was actually a workshop on conceptual modeling. I arrived late (I’m so exhausted from this conference, I didn’t expect that). When I arrived, Dr. Heavey was presenting his work, and he discussed various approaches studied. These included Petri Nets, and UML State Machines. After his talk, I commented on how UML state charts are very similar to what he was describing. This brought an eruption of laughter from the audience, although I had not finished my comment and question. It was rather annoying, since YetiSim uses a modified version of UML for modeling. I expect that at least some parts of YetiSim’s execution graphs could be useful. You see, this is why they are not called state machines anymore, and are execution graphs now. People presume that they know what you are talking about, when you say “modified version” they don’t ask how it is modified, they assume it’s something small, not a radical shift of ideas. During the break, I obtained some contact information for Dr. Heavey. I would like to learn more about his work, and I intend to read his paper. However the break time conversation was dominated by discussions of the problems, with an emphasis on why UML is horrible for modeling. I admit I don’t have enough of a background in conceptual modeling to have an intelligent argument, but I would have enjoyed the conversation. This is why I shouldn’t use the word UML and will never use the word “state diagram” in association with how YetiSim runs.
The workshop featured other presentations, including one from Boeing and NATO. The talk from NATO was interesting, and the presenter outlined their goals. The presenter from Boeing was very energetic, although the bottom of his slides had something stating to the effect that disclosure of details was forbidden except under conditions presented in the title slide (which I wasn’t in the room to see). In my opinion, such disclaimers have no place at an academic conference They belong to select groups behind closed doors. The presentation from Boeing was very interesting, I just didn’t like the caption at the bottom of the slides. It’s interesting just to hear how much Boeing uses simulation.
Otherwise, I checked out of the hotel today and spent some time reading before departing on the train back home (which is where I’m writing this right now). Deborah has expressed interest in forming a working group at U of T on conceptual modeling. I think that would be a great idea, and the work of the group could benefit both YetiSim, and give an opportunity for U of T to become more involved in simulation. U of T is fairly open to interdisciplinary pursuits in my experience, and it would be wonderful to have a group composed of engineers, computer scientists, cognitive scientists, and others to examine methods of simulation modeling.
Another problem with YetiSim came up today. It has no ability to pre-empt tasks. I have to figure out a solution to this one. Also the interconnection of entities is not something that has been well planned, when you have things that are interacting with each other. The example presented was a tug boat and a tanker, which require interactions with each other for an effective simulation.
A few presentations discussed semantic web, and it sounded like something interesting to explore.
Overall it was an interesting experience, this was my first conference. I look forward to collaborating in future with the people I met at the conference.
Today I attended a talk on DEVS. The presenter implemented a DEVS-RMI model for his PhD. It was early in the morning and I was tired, others were yawning too (it was a late night). The presentation didn’t focus enough on DEVS itself, it was supposed to be a tutorial on DEVS, instead it was a sales pitch for DEVS-RMI. I don’t know anything about DEVS, so it was tricky to follow although I got some interesting ideas. Some of the slides were missing labels on the axes, so it was really hard to figure out what I was looking at. From what I saw about DEVS, it looks interesting although overcomplicated. I want to look at ADEVS and CD++ to see how they implement time increments. I’d also like to benchmark YetiSim against them to see how it performs. DEVS seems to lack parallelization within its formalism, so that would be a problem. One question I had, that wasn’t answered by the presentation was whether or not the DEVS formalism can implement a Turing machine. I suppose that a Turing machine can be simulated, but it’s not quite the same. I suspect that since DEVS is based on state transitions, this is not the case. I will have to research further to understand this. The DEVS tutorial really pushed the point that the simulator could be separated from the model and system, and I took that to mean the class design and simulator.
This presentation let me see something in YetiSim I overlooked…I have no method of obtaining a signal from the outside environment without waiting for it explicitly. It just occurred to me during the discussions that I forgot to plan for this functionality. Another part of the talk that was interesting was the fact that DEVS can model both continuous and discrete systems.
Deborah and I presented YetiSim today. Unfortunately the conference did not organize the poster presentations well, so only a few people really attended it. The poster session was hosted during sessions, and the coffee for the break was in a different room. I didn’t get the audience I had hoped for, but ah well enough people were interested!
I talked with someone who had a very interesting insight, he labeled YetiSim as an “application level virtual machine”, which is a very good description of it. Although YetiSim lacks an interpreted language, in a sense it’s acting as if it is interpreting bytecode. I wonder if YetiSim could therefore do something like a JIT compiler? An interesting concept, that I could extract the code I needed, compile it, and dynamically link it in at runtime… and voila I have something that gets faster! The cost of compilation would have to be recovered however…. although I could certainly allow the user to pre-compile their execution graphs…. an interesting concept indeed…
I received a lot of feedback. The parallel performance of YetiSim was a disappointment for many, and I expressed that this is the exact reason why research is ongoing. With sufficient tools, YetiSim will improve. I already have so many new ideas for how to improve performance from peer feedback, it was really nice to have other simulation people to talk to. I definitely feel like we are going in the right direction, although I see there are things YetiSim doesn’t do yet that it really should. I’m anxious to get a new computer to continue to work on YetiSim. More people were actually interested in TBB than YetiSim though.
After the poster session, I went out with Dr. Buyya for the evening. We walked to Hull, and back to Ottawa. We also discussed GRID computing and what GRID-enabled simulation would look like. We disagree a lot on how GRID technologies should be implemented… strongly disagree actually. Dr. Buyya is a strong advocate of GRID technologies implemented in .NET, and this is the wrong approach to me. Quite simply, I do not trust any corporation which would flaunt software patent violations without merit, and threaten the industry with lawsuits. Perhaps I have a prejudiced against .NET for fear of company software patent intimidation, and hence the potential problems with the use of mono. If I were implementing GRID stuff, I would be using Python and C++. Language and platform debates will always be there, but we agreed on concepts. We went for dinner at an Indian restaurant, it was pretty good (but spicy, and I wasn’t used to it).
This week I am attending the SCS Spring Sim ‘08 conference in Ottawa, Ontario. This is the first conference I have attended, and tomorrow Deborah and I are presenting a research poster on YetiSim. Along with the poster, a short paper on YetiSim has been published with the proceedings of the conference. I have been to Ottawa a few times, so I wasn’t too excited to see the city, but next year the conference is in San Diego which would be neat.
I attended a talk by Dr. Rajkumar Buyya about GRID computing and GRIDSim. I remember looking at GRIDSim some time ago, when I originally researched GRID and Beowulf simulators. It is implemented in Java, so the performance of the simulator likely will not be very efficient, at least if it is a discrete event simulation with a large number of entities. I also attended the keynote talk, but it was early in the morning and I needed some coffee (apparently in short supply here). The keynote talk focused on psychology experiments with the effectiveness of HUDs on reaction time. Unfortunately not quite in my interests, but there were some pretty pictures, and it would be neat to play with a helicopter simulator just to see how quickly I crash it.
This afternoon I had a break from proceedings, since there weren’t any papers that looked very interesting (and my attention span is really short I’m afraid, unless the topic is super interesting). I met representatives of CAE today during my break. Their research and products seem to be inline with the type of simulation work I am doing. It looks like it would be an interesting place to work for a summer, but I wouldn’t sign a contract which limited my ability to work on YetiSim, so it wouldn’t be likely. I also met some people from Concurrent who gave me a Tux penguin toy (which I like very much). They are doing a real-time Linux operating system, but they do some type of electronics simulation that gave me an interesting idea. Really what they do, is allow simulated electronic inputs or something to be part of the simulation (sorry, attention span is skipping some of the details there). But anyhew, YetiSim could easily be extended to receive input from virtual devices or real ones for simulation by allowing the state executions to be an input. Wouldn’t be that bad to do actually, and might still benefit from parallel processing.
I got a lot of interest in YetiSim today, and sat down with professors from Dalhousie and Victoria University. I met a few people who are interested in health care simulation, Deborah’s field of research. We went over YetiSim in great detail for about an hour and a half. It would be awesome if I could get funding for the summer to just work on YetiSim full time, there seems to be some excitement about it. We’ll see tomorrow when we do our actual presentations what the interest level is. I hope that people will be as excited about YetiSim as I am. I’ve actually been surprised how interested people are in something like YetiSim which is open source and all about performance. It’s very encouraging.
I met Dr. Buyya, which I discussed a bit earlier. A very nice man from the quick conversation I had with him, I’d like to spend some time with him to just discuss ideas. I actually had considered doing my masters with him at one point, maybe I still might who knows. I would love to study in Australia. An interesting conference overall, not enough food though, or social events to mingle. Lots of ideas and energy floating around though.
Yesterday I discussed a problem with processing interdependent entities with TBB. This doesn’t just pertain to simulations and to the execution_graph, but in general. There is no provided high-level construct which allows you to easily process elements of a range with interdependencies. Let me see if I can say this more clearly, say I have to process a collection of entities, but I also have to reprocess some of those entities over again in the algorithm. Perhaps I am processing 2D cells on a map, and have to complete a second pass to process the boundaries. This could certainly be done with the task_scheduler, and likely could be done with just the range and partitioner.
I am interested in a high level construct which would allow me to partition a set of elements into units which could be processed in parallel. This construct should then allow me to partition the set again to make another pass, and so on until I deem that the processing is completed. In this way, the problems discussed in Part 3 of my blog series on the execution_graph could be resolved. I know I promised code yesterday, but I’ll just show an idea today.
In order to ensure I’m conveying my ideas effectively, I’ve prepared some diagrams. Suppose I have a set of elements to process in some manner. I’ll represent this set as blobs of ink on a digital page, as shown below.
In order to process these elements, in the first pass I might partition the space into three segments. I do not have to process the entire space at once, just the segments which interest me. I’ve drawn lines around the elements I want to process. These three partitions should be processed in parallel.
Again after processing these segments I might not have completed my task. Next I will partition the space into another three segments which can be processed independently. Note that this time one of the segments only contains a single element to process, this is fine and entirely possible.
For the last step, I will partition the space one final time into two large segments. Once again these two segments will be processed in parallel.
I call the construct which will support this (tentatively), parallel_set_for. This conveys that we have a set of elements which are to be processed. We process subsets of this larger set independently, then partition the larger space into subsets again for further processing until the task is completed (as opposed to partitioning the subsets into smaller ones).
In contrast with the TBB parallel_for construct which simply divides elements for individual processing, the parallel_set_for construct might not even process all elements. Some might not affect computation so they might be omitted. Furthermore, the parallel_for construct is designed to divide work to keep all processors busy and simply complete after all elements have been processed. The parallel_set_for construct would proceed in steps, where independent subsets are selected and then processed.
In comparison to parallel_for, this processing method could form a bottleneck. If partitions are not selected properly, effort might be wasted because some partitions could have been processed in a previous step. In addition, a single element which is being processed might hold up multiple independent partitions which could process next without affecting results. I think that this could be compensated for with good interface design.
Well, that is what I’ve thought up so far. I welcome your comments. This is not a fully thought out idea, just an idea which sprung to mind today that I wanted to share with you. Good night!
I hoped to have written some skeletal code by now to show you, and start to point out the classes. However I find when I take on a software design, that I start to think about it a lot. I ponder how things interact while I’m in the shower, or find myself visualizing the program interactions, daydreaming while I’m cooking dinner or doing dishes. The past weekend has been filled with these moments, and now I’ll share my thoughts with you.
First, the class name transition is again misleading. I need a better name to represent the connections between nodes in the execution graph. The name link, or execution_path best convey the meaning. This is a small matter, but I wanted to give you the heads up.
Now, I’ll describe my thoughts over the weekend. Prepare yourself for a rant, and of course post comments if you have some ideas. The question is, what does the execution_graph execute… when it is “executed” something should be passed as an argument so that the execution_graph can base its decisions upon something. This might be an open file descriptor, an entity in a simulation, or perhaps absolutely nothing. Perhaps the decisions to make are programmed within the links themselves so arguments are not required. So let’s just pass a single thing, and even better let’s template this argument so a list of things could be passed. The state machine (I mean execution_graph) might be associated with one particular type, say ExecutionArgumentType.
This idea works well if we have a collection of things to process individually, say file descriptors for sockets. Each socket might be passed to an execution_graph for operations to take place. We can do even better, and use tbb::parallel_for with the auto_partitioner to divide up a vector of sockets and run their execution_graph in parallel. This is great for such easy examples, but what happens when we can’t do such a trivial division? What if we are processing something that requires fuzzy boundaries when we partition a space. For example, say we divide up a 2D plane into rectangles, and we have an algorithm which requires input from neighbors in a 2D cell for proper execution, like Conway’s game of life.
This is something that really ought to be handled by an execution_graph, but it’s not so easy unless the entire 2D board is passed as an argument. So the execution_graph can’t really do this kind of processing yet. But I’m not here to write Conway’s game of life in the execution_graph, I really don’t know how somebody would do it yet… but this doesn’t change the fact I need to give them the tools to do so. In my mind, I need to find a clever way of letting people smarter than me to do clever things with my constructs.
This is an open problem, I’d love to say I knew how to do this. The reality is, I will likely abstract the problem away into a class which breaks apart a larger chunk into smaller ones for processing, just like the TBB Range concept. It may be that I use that, but I’m not sure the interfaces are sufficient. People can then use this class in clever ways.
This brings me to the other subtopic in my blog title: dividing work. I need to provide users with a method by which they can determine which execution_graph gets what job, or at least dividing up a pile of work to do. I have a feeling that the solution to this problem will be incorporated with the former problem I stated, which is how to determine boundaries during processing.
That’s it for now, I’ll post another blog tomorrow night to keep you up to date with my design thoughts, and perhaps some code tidbits! Once things get more concrete, conversations should be a bit easier. It’s hard to convey my thoughts when I haven’t thought them all yet.
I decided today that the name state_machine is too deceptive, and resolved to find a better name. The term state machine is particularly deceptive because nodes are not required to be states, but can execute complex logic internally. After some brainstorming, I came up with the new name execution_graph. This conveys that the construct is a graph which is associated with program execution. I have also decided to remove the state node type, and replace it with two types: compute and IO. The intention behind this is that some execution stages will be IO intensive whereas others will be computationally intensive. Differentiating behind the type of complexity entailed will be of benefit when TBB supports parallel IO operations. For now, there will be little if any difference.
In my first implementation of a state_machine (the predecessor to the execution_graph) I relied heavily on polymorphism and dynamic_cast. I discovered two problems with this approach. First off, I only required the polymorphism in the state node class which contained logic to execute. Second, I used dynamic_cast to evaluate node types at run time which degrades performance with unnecessary overhead. In reality separate classes are not required if each node type is permitted to contain functions which are executed upon visitation of that node. This is a bug disguised as a feature. I don’t know why somebody would want a join node or fork node to execute logic upon visitation, but it simplifies the interface. I’m getting ahead of myself, let me identify the critical components I see and discuss how I envision an implementation.
This will be a template class, but more on that later. This class will be the main user interface and will provide facilities for the construction of a graph in which nodes contain functions that will be executed during evaluation at runtime. It will own all transitions, nodes, and execution instances. These owned objects will all be destroyed if the instantiated execution_graph goes out of scope, so it is up to the user to ensure it remains in scope for proper execution. Users will be provided with a function like getStart() which will return a start node for them to use to build the execution graph. The logic for the evaluation of the graph itself (that is, how the graph is traversed and executed) will be provided as a template argument for maximum flexibility, along with some other classes.
The node class represents a particular node within the execution graph. It could be a compute, join, fork, IO, start, final, or error node. Each node instance may only be created by another node instance, so users may not arbitrarily create them. Also, nodes will contain a pointer to the execution graph which they are associated with, so that transitions may not be created between nodes in separate execution graphs. The node class stores several functions which are called with appropriate arguments during graph execution. The declaration for the variable type which stores the function is to be provided as a template argument for maximum flexibility (e.g. I might want to use boost.function, others might want to use raw function pointers). The argument type which is provided to the stored functions is also provided as a template argument.
This class will represent a transition between nodes in the execution graph, which might be guarded or unguarded. The transition class will be provided as a template argument to the execution_graph, since others might want their execution_graphs to have special transitions. For example, YetiSim will alter the execution_graph transition logic so that simulation time is advanced by special transitions. Rather than adjusting internal implementations of a transition class just for YetiSim, by providing it as a template argument others may customize the behavior of the execution graph.
This class encapsulates graph execution logic, and is provided as a template argument to execution_graph. This class will determine the parallelization strategy used in evaluation of the execution_graph. It will also determine how transitions are handled, so if a user overrides the default transition class they will also have to adjust the execution_logic class. The main idea for this class, is that it will provide certain required functions to the execution_graph which drive actual execution.
Not so long ago, I wrote a blog about the fact that I am separating the YetiSim state machine architecture into a generic component for contribution to the TBB project. I have no idea whether or not this component will be accepted by TBB officially, however others may find it useful so I am blogging about my design as I go. I use the term state machine to describe the construct I am building, but this is misleading. In August 2007, I started the research that lead to the YetiSim state machine construct, however it has evolved into something more sophisticated and without a proper name. Let’s start from the beginning and illustrate the initial motivations for the construct and what it does for us now.
I first looked toward TBB as a platform independent C++ threading library which could be used as the foundation of a simulation framework. Initially I was searching for a method to save and restore the stack, hence emulating coroutines for simulation. I was disappointed to learn that not only does TBB not provide any such low-level method, the usage of such methods is actually discouraged. After much thought, I realized that I could implement a state machine to provide the functionality which I required. The state machine would consist of start, final, error, fork, join and state nodes. I’ll give a brief description of the intended role of each node.
Each node has a corresponding symbol which I will not include here. These node types are based off state machine nodes found within UML. The nodes are joined by transitions which are either guarded or unguarded. The basic motivation is that an unguarded transition is always taken, whereas whether or not to proceed along a guarded transition is determined at runtime. Already I have omitted a critical detail, execution of the state machine proceeds literally. I will describe execution next.
When a state machine is executed, a pointer is created which points to the single start node within the state machine. Execution logic determines how execution proceeds by evaluating transitions and following them accordingly. Each node has a special meaning, and execution logic must take this into account while traversing the state machine. When a fork node is encountered, multiple pointers are created which might traverse the state machine in parallel. Similarly, join nodes indicate that multiple execution pathways should be tied together before execution proceeds. The join node will wait patiently for each execution pathway that can reach the join node to do so, and proceeds after that point.
In my opinion, the execution of a state machine will not have a significant runtime cost. The execution of a state machine provides a functionality that replaces the requirement for coroutines within simulation, since a transition might indicate that execution should not proceed until the simulation clock has been advanced by a certain amount. Similarly transitions might indicate probabilities, providing a functionality like that of a Markov chain. Since the logic of the state machine is dictated by the connections of nodes, they may be altered arbitrarily and potentially at runtime. This permits a highly dynamic programming environment with minimal additional cost. Keep in mind that saving and restoring the runtime stack would also have a significant runtime cost, and might require operating system calls. The state machine construct does not require any such calls, and should execute faster.
Earlier I described the name state machine to be misleading. This is because each state node may embed any logic, and not just represent a particular state. This construct is thus a superset of a state machine. Execution may proceed in many possible manners. Furthermore this state machine is easier to maintain than state machines implemented with switch logic. The adjustment of state machine logic does not have a high cost here, because only the representation of the state machine must be altered. A good design which incorporates the state machine concept will not require a reimplementation of existing code, rather just adjustment of transitions.
This construct is highly useful for simulations, but equally useful in other contexts. For example, this state machine might be highly useful for controlling parallel I/O when TBB itself supports it. It might also be the foundation for such an I/O library. Each state node might be labeled as computationally or I/O constrained and TBB could then manage the low-level details to ensure efficient execution with these hints. It also provides a simple interface to the TBB scheduler, and might permit designers to exploit parallelism in constructs that otherwise might be more complex. In fact, complex logic could be dissected into smaller chunks with this construct and represented easily as a system of nodes and transitions. This allows close inspection of the logic, and discussion with others to ensure that the system designed and requirements match properly. It is not difficult to construct a graphviz representation of the state machine, so it is fairly simple to inspect this logic visually to ensure proper execution.
I realize that programming languages and the computer execution itself may be considered to be a state machine. This is certainly true at a theoretical level, however adjustments to logic generally require a recompilation of source code. The state machine construct I propose has an easier method of dynamic adjustment. The state machine construct provides something like lego blocks, and thus allows users to assemble the pieces in any way they see fit.
Finally a theoretical discussion. The state machine construct I propose is deterministic. Although it appears similar to a Finite State Automaton (FSA), it is not. This state machine is capable of computation within its nodes, and has more node types than a FSA as well. The two are related, but are not identical.
YetiSim now has a sourceforge page! Check it out http://www.sourceforge.net/projects/yetisim. The majority of content will continue to be hosted at yetisim.org, however YetiSim now has mailing lists which are hosted by sourceforge. You can subscribe to the mailing lists here: http://sourceforge.net/mail/?group_id=215087
I would encourage anyone with an interest in YetiSim to subscribe the appropriate list. This would be encouraging for me personally as a developer, and you can of course unsubscribe at any time. I would love to get feedback from others on how YetiSim could be improved, or what features could make it better.
In the original YetiSim state machine implementation, I used polymorphism to represent the various types of nodes that could occur within the state machine. Each possible node type (Start, Final, Error, Join, Fork and State) was derived from a generic Node class. I implemented convenience functions like bool isStart(Node* node) { return dynamic_cast<Start*>(node); } to determine node types to drive the state machine execution algorithms.
I later realized that polymorphism was not required, and that I could implement a single Node class which contained an enum which identified the type of node. This could eliminate the need for calls to dynamic_cast with a relatively small increase in programming complexity. The curious cat that I am, I wondered if this implementation would have better performance than dynamic_cast for large data sets. I wrote a sample application and timed the dynamic_cast against just looking up with an enum, and found that dynamic_cast indeed was slower. However, with the -O2 optimization flag passed to gcc dynamic_cast seemed just as efficient.
The question now is whether or not all compilers will optimize dynamic_cast in the same way as gcc. Could it be that this simple application was easily optimized, whereas a large scale program will show a performance hit with dynamic_cast? These are questions I’d like to find answers to, however at this point the simple fact of the matter is that dynamic_cast must be executed at runtime to ensure the types are correct, whereas static_cast does not require any runtime overhead. So, instead of relying upon compiler optimizations, I’ve decided to go ahead with the enum and static_cast solution.