> 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 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
