I did not know what, "dynamic space decomposition algebras," meant so I looked it up. The Wikipedia page I found was in the language of abstract algebra and I could not understand what they were getting at. However, I found this paper which the authors called, "A tertiary-tree-based dynamic space decomposition approach," and found that it made a lot of sense to me.
An interesting point is that since the containers come in too many different variations to make an efficient algorithm they started with (what I have called in the past) a conveniently finite set of container sizes, If I understood the authors they then pre-computed how spaces smaller than most cargo holds were could be filled with variations of these simplified containers and how different combinations of these smaller spaces could be fit together. So it looks like the typical dynamic space decomposition algebra would have to be a heuristic composed of simplified sets of objects. But this in turn would typically lead to systems which did not conform to equi-incremental systems meaning that many useful functions could not be superimposed on the system. (Dimensional functions are based on continuous incremental measures so they don't lead to skips in the potential volumes. I am pointing out that even the dynamic decomposition algebras, which are more efficient than piecemeal trial and error, will not typically lead to further refinements in efficiency because they have to use non-continuous, non equi-incremental objects.) A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach http://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=1067&context=odettepub&sei-redir=1&referer=http%3A%2F%2Fwww.bing.com%2Fsearch%3Fq%3Ddynamic%2Bspace%2Bdecomposition%2Balgebras%26qs%3Dn%26pq%3Ddynamic%2Bspace%2Bdecomposition%2Balgebras%26sc%3D0-0%26sp%3D-1%26sk%3D%26cvid%3D95655503125b48648b7ca4468fde5719%26first%3D9%26FORM%3DPORE#search=%22dynamic%20space%20decomposition%20algebras%22 Jim Bromer On Tue, Aug 18, 2015 at 2:22 PM, J. Andrew Rogers <[email protected]> wrote: > > On Aug 18, 2015, at 10:12 AM, Logan Streondj <[email protected]> wrote: > >> >> >> It generally involves three design characteristics; (1) using data >> structures that never require reorganization of your data i.e. no hash >> tables or range partitioning, >> > > some examples would be nice, > but I guess you mean to prefer simple and data-structures, like strings > and arrays. > > > > No, distributed structures based on dynamic space decomposition algebras. > It is like having a lot of secondary indexes on your data without having > any secondary indexes, which is good because secondary indexes do not > scale. Currently the most expressive/scalable type of data structure that > exists. There is no academic literature on them and the first versions were > only invented about a decade ago, modern versions only in the last five > years. They are being used in a handful of big systems already. > > You can look at a strict, binary quad-tree as an extremely narrow and > special case of these structures. > > > (2) logically generating uniform “work units” of compute that exceed the >> number compute elements by at least a couple orders of magnitude, and >> > so you mean each processing-core should have a queue of 100 or more > similar operations. makes sense, to justify the cost of core set-up > > > > The operations do not need to be similar, just related to data that is > wholly owned by the core. You move operations, not data. The point of > having thousands of independent work units is that a core can continuously > and dynamically reorder their execution to maximize throughput and to allow > easy load balancing. > > > > >> (3) have every compute element independently and dynamically schedule its >> own work sequence using game theory to orchestrate instead of explicit >> coordination. >> > > Okay I understand a core scheduling it's own work from a queue, but not > sure what you mean by using "game theory" which is a rather broad concept. > > > > > This is something that only works if you schedule your own I/O. Operating > system I/O schedulers are oblivious to what is going on around them and > routinely make pathological I/O scheduling decisions from a global point of > view. > > The concept came from routing theory and has been around for ages, I have > no idea who invented it. Given that a core explicitly schedules and orders > all of its communication and execution *and* that the core can assume all > other cores are running a similar scheduler, it is possible to design a > scheduling protocol that ensures approximately optimal aggregate throughput > and minimal conflict for the entire system. Essentially, each core > schedules its activity based on a protocol that models the state of other > cores it interacts with to minimize the probability of conflict or > bottleneck with minimal explicit information exchange. > > I have seen variants of this for both single multithreaded processors and > big distributed systems. I love the cleverness of it. Each thread makes a > decision on what to do next on a very fine-grained basis based on a model > of what all the other threads are deciding in their individual contexts in > the same shared environment. You still have to detect contention but the > amount of contention that occurs is *much* lower than in explicitly > coordinated systems because the threads are actively avoiding each other > without any detriment to their individual throughput. > > To be honest, I know the idioms for this kind of thing just well enough to > apply them. The mathematics underlying it is somewhat beyond me. > > *AGI* | Archives <https://www.listbox.com/member/archive/303/=now> > <https://www.listbox.com/member/archive/rss/303/24379807-653794b5> | > Modify > <https://www.listbox.com/member/?&;> > Your Subscription <http://www.listbox.com> > ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
