I ran across a concept called "self-organized criticality" while investigating chaos. The term refers to simple systems that nonetheless give rise to critical points. The original investigation I believe was of pouring sand onto a surface, which builds up into a pile, and occasionally causes avalanches.
In computing, this could be represented by balanced trees, cellular automata, and similar structures.
If such programs give rise to unpredictable critical points, then this could cause chaotic allocation behavior from a simple program.
Thursday, July 30, 2009
Sunday, July 26, 2009
Current Questions on Garbage Collection and Chaos
My investigations into garbage collection and chaos have produced two main areas of interest so far. Both are motivated by the previous question of "how can one choose the points at which to perform collections wisely?"
First, garbage collection actions by definition, have no effect on execution from the standpoint of semantics. Collection actions replace the memory graph with a subset of the same memory graph, which is isomorphic with respect to the root set. Therefore, collections can be performed anywhere during execution. Typically, there is a maximum size which garbage collection must keep the program under.
Assuming that the cost of collection is roughly equivalent to the number of objects preserved, then we can usually have a profound impact on the total cost of collection depending on exactly where we perform collections. There are three general schemes for doing this:
1) The perfect world, where we know the execution ahead of time, and we pick collection points using arbitrary computing power. This is obviously unrealistic, but it's the goal. This is a basic constraint-solving problem, and it yields the optimal result. Call this mode "hindsight".
2) We know the program ahead of time, and can do arbitrary full-program analysis, compilation, and the like, but we don't know the specifics of any execution. Call this mode "full-program".
3) We don't know anything about the program. Call this mode "online".
The first major question is whether there is a gap between hindsight, full-program, and online. I suspect there is. Specifically, I'm almost certain that hindsight > full-program, and I'm pretty sure full-program > online.
The second specifically concerns the full-program scheme. I'll call programs whose execution patterns and allocation patterns are predictable knowing all inputs "regular", and those who aren't "chaotic". It's pretty obvious that you can have a regular program with regular allocation behavior. An example is a program that builds up a list to a specific length, then empties it, then fills it again. Once you know the length of the list, you can plan to do collections when you empty the list. I'm almost certain that one can produce a chaotic program with chaotic allocation behavior by adapting a real-life chaotic system like Lorenz's water-wheel. It's fairly easy to get from this point to chaotic programs with regular allocation behavior. The real question is, can you have a regular program with chaotic allocation behavior.
On that, I'm split. Intuition would seem to say "no", but there is alot of work on things like chaotic iterated maps that leads me to suspect otherwise.
So the real second question is whether or not a regular program can produce chaotic allocation behavior.
First, garbage collection actions by definition, have no effect on execution from the standpoint of semantics. Collection actions replace the memory graph with a subset of the same memory graph, which is isomorphic with respect to the root set. Therefore, collections can be performed anywhere during execution. Typically, there is a maximum size which garbage collection must keep the program under.
Assuming that the cost of collection is roughly equivalent to the number of objects preserved, then we can usually have a profound impact on the total cost of collection depending on exactly where we perform collections. There are three general schemes for doing this:
1) The perfect world, where we know the execution ahead of time, and we pick collection points using arbitrary computing power. This is obviously unrealistic, but it's the goal. This is a basic constraint-solving problem, and it yields the optimal result. Call this mode "hindsight".
2) We know the program ahead of time, and can do arbitrary full-program analysis, compilation, and the like, but we don't know the specifics of any execution. Call this mode "full-program".
3) We don't know anything about the program. Call this mode "online".
The first major question is whether there is a gap between hindsight, full-program, and online. I suspect there is. Specifically, I'm almost certain that hindsight > full-program, and I'm pretty sure full-program > online.
The second specifically concerns the full-program scheme. I'll call programs whose execution patterns and allocation patterns are predictable knowing all inputs "regular", and those who aren't "chaotic". It's pretty obvious that you can have a regular program with regular allocation behavior. An example is a program that builds up a list to a specific length, then empties it, then fills it again. Once you know the length of the list, you can plan to do collections when you empty the list. I'm almost certain that one can produce a chaotic program with chaotic allocation behavior by adapting a real-life chaotic system like Lorenz's water-wheel. It's fairly easy to get from this point to chaotic programs with regular allocation behavior. The real question is, can you have a regular program with chaotic allocation behavior.
On that, I'm split. Intuition would seem to say "no", but there is alot of work on things like chaotic iterated maps that leads me to suspect otherwise.
So the real second question is whether or not a regular program can produce chaotic allocation behavior.
Tuesday, July 21, 2009
The Differences of Asynchronous Complexity
After finishing rewriting my paper on this subject for PPoPP, several things are apparent:
1) CAS, LL/SC, or bounded-size transactions are the fundamental operation, not consensus. Consensus objects, because they are one-shot objects, end up increasing costs.
2) The lack of a universal construction is problematic. However, I doubt that such a construction can truly exist, at least for all kinds of objects.
3) The hierarchy emerges from the number of simultaneous CAS operations needed to implement a given data structure. At the moment, I've considered only constant number of operations. However, in a distributed object framework or transactional memory system, we might see something like a binary tree has a simultaneity of O(log2(n))
4) There may be a complexity gap between lock-freedom and wait-freedom. I suspect it to be O(n).
1) CAS, LL/SC, or bounded-size transactions are the fundamental operation, not consensus. Consensus objects, because they are one-shot objects, end up increasing costs.
2) The lack of a universal construction is problematic. However, I doubt that such a construction can truly exist, at least for all kinds of objects.
3) The hierarchy emerges from the number of simultaneous CAS operations needed to implement a given data structure. At the moment, I've considered only constant number of operations. However, in a distributed object framework or transactional memory system, we might see something like a binary tree has a simultaneity of O(log2(n))
4) There may be a complexity gap between lock-freedom and wait-freedom. I suspect it to be O(n).
Sunday, July 12, 2009
Defining Lock-Freedom for Synchronous Channels
The problem on my mind now is trying to find a definition similar to lock-freedom for synchronous channels. The real problem I want to describe is the concept of implementing synchronous channels with choice-composition without using a global lock.
Herlihy's definition of lock-freedom is nice, because it eliminates the capacity for blocking synchronization generally, by stating the property that you really want: at least one thread is guaranteed to finish. Unfortunately, it doesn't quite work for synchronous channels, which are inherently blocking.
There are three approaches I've considered:
1) Try to define the exact properties that global locks have. This is near impossible, and I can actually visualize Herlihy's original thinking through the papers about linearizability and lock-freedom (he was my advisor afterall). Trying to state what is forbidden is near impossible. It's better to go for what you want.
2) Try to define some sort of synchronization operation which can only synchronize two threads. I'm pretty sure this is impossible.
3) Expand lock-freedom to accomodate synchronous channel operations. This seems most promising. My thoughts are something like "assuming there is a possible solution, one thread completes in a finite amount of time".
The third will probably be the one that I end up selecting.
Herlihy's definition of lock-freedom is nice, because it eliminates the capacity for blocking synchronization generally, by stating the property that you really want: at least one thread is guaranteed to finish. Unfortunately, it doesn't quite work for synchronous channels, which are inherently blocking.
There are three approaches I've considered:
1) Try to define the exact properties that global locks have. This is near impossible, and I can actually visualize Herlihy's original thinking through the papers about linearizability and lock-freedom (he was my advisor afterall). Trying to state what is forbidden is near impossible. It's better to go for what you want.
2) Try to define some sort of synchronization operation which can only synchronize two threads. I'm pretty sure this is impossible.
3) Expand lock-freedom to accomodate synchronous channel operations. This seems most promising. My thoughts are something like "assuming there is a possible solution, one thread completes in a finite amount of time".
The third will probably be the one that I end up selecting.
Wednesday, July 1, 2009
Garbage Collection and Chaos
Changing topics, and going to more research in progress as opposed to finalizing what I've already done. I'm shifting to my long-term work: chaos and computing.
The original question was "is garbage collection chaotic?" Now that I understand all this better, I can take a more direct approach. For a system to be chaotic, three properties need to be satisfied.
1) Sensitivity to initial conditions
Points which are close to eachother may produce substantially different trajectories. That is, subtle changes may drastically alter the result. This, I think, is the most important.
2) Topological mixing
As near as I can tell, given any two sets of points, it is possible to start with any point in one, run the system long enough, and end up with a point in the other.
3) Dense periodic orbits
Repeating orbits are continuous, or unbroken. You don't don't have "gaps" in a cycle.
Now, how does this relate to garbage collection? That depends on what you're measuring. My first thoughts were to treat a family of isomorphic memory graphs as a single point in a space. However, this will not be a chaotic system. Garbage collection as a system will consist of a number of families of isomorphic graphs with vectors all pointing towards a set of strongly-connected graphs representing the nodes reachable from the root set. Clearly this is not chaotic.
The costs of collections, however, may well be chaotic, or determined by some chaotic system. Costs can be measured in terms of nodes traversed, nodes deleted, nodes preserved, or some combination thereof. An individual move from one graph to another entails some cost.
Now, a program describes some trajectory in this space of graph-families. At some interval, the garbage collection function gets fired, which costs something. Depending on how costs get computed, two neighboring points (graphs) in the trajectory described by the program might result in radically different collection costs. So whatever function decides when to collect can potentially have a major effect on the total cost (this is something analogous to sensitivity to initial conditions). Topological mixing and dense orbits are more troublesome. They suggest the ability for a given decision function to produce arbitrarily bad behavior if the program runs long enough.
I think the more telling question is "how much data is necessary to make optimal, or within some multiple of optimal decicions about when to collect?", or perhaps the other angle, "how close to optimal can I get with a finite data set?". Can a collector actually make a decent decision, or will it produce arbitrarily bad behavior given enough time? I think answering that question would get at the original intent.
The original question was "is garbage collection chaotic?" Now that I understand all this better, I can take a more direct approach. For a system to be chaotic, three properties need to be satisfied.
1) Sensitivity to initial conditions
Points which are close to eachother may produce substantially different trajectories. That is, subtle changes may drastically alter the result. This, I think, is the most important.
2) Topological mixing
As near as I can tell, given any two sets of points, it is possible to start with any point in one, run the system long enough, and end up with a point in the other.
3) Dense periodic orbits
Repeating orbits are continuous, or unbroken. You don't don't have "gaps" in a cycle.
Now, how does this relate to garbage collection? That depends on what you're measuring. My first thoughts were to treat a family of isomorphic memory graphs as a single point in a space. However, this will not be a chaotic system. Garbage collection as a system will consist of a number of families of isomorphic graphs with vectors all pointing towards a set of strongly-connected graphs representing the nodes reachable from the root set. Clearly this is not chaotic.
The costs of collections, however, may well be chaotic, or determined by some chaotic system. Costs can be measured in terms of nodes traversed, nodes deleted, nodes preserved, or some combination thereof. An individual move from one graph to another entails some cost.
Now, a program describes some trajectory in this space of graph-families. At some interval, the garbage collection function gets fired, which costs something. Depending on how costs get computed, two neighboring points (graphs) in the trajectory described by the program might result in radically different collection costs. So whatever function decides when to collect can potentially have a major effect on the total cost (this is something analogous to sensitivity to initial conditions). Topological mixing and dense orbits are more troublesome. They suggest the ability for a given decision function to produce arbitrarily bad behavior if the program runs long enough.
I think the more telling question is "how much data is necessary to make optimal, or within some multiple of optimal decicions about when to collect?", or perhaps the other angle, "how close to optimal can I get with a finite data set?". Can a collector actually make a decent decision, or will it produce arbitrarily bad behavior given enough time? I think answering that question would get at the original intent.
Subscribe to:
Posts (Atom)