Dan's crazy ideas #2 - Parallel processing

Continuing the discussion from Dan's crazy ideas #1 - Collaborative contest:

You thought I went away, that I was beaten back into the hole that I had emerged from! Stop the madness!

No! I will not back down! Madness ensues…

Concept

Join any decently large software project, and you will need to come to grips with parallel processing. Even if your project is single-process, single-thread, I guarantee that at least the discussion will come up.

Sidetrack to Dan’s silly little anecdote… I once worked on a very complex, multi-tiered behemoth of a project where each tier was under the control of a separate corporate organizational group… One day the walls came down, and all groups became one, and I found that one of the tiers was designed such that it spawned literally hundreds of threads at startup, and all but a few of them spent the vast majority of their life blocked on a pipe read… :open_mouth:

Okay, I’m back. So CG allows for the use of threads, but your code only has access to a single CPU, so multi-threaded code is never helpful.

Proposal

Simple enough. I think it would be cool to have a specific puzzle, or category of puzzle, or competition… what have you, that focuses on the use of parallel processing.

Disclaimer: Yes, I know that this will likely strain processing resources, and might make this proposal untenable.

Here are a few ideas for how this could be implemented:

  1. Create a competition that is algorithmically intensive, as opposed to strategically intensive (i.e. STC rather than CB). Explicitly give entrants access to more than one CPU, and let them have at it.

  2. Similar to #1, but as a puzzle. Create a puzzle that simply cannot be solved with a single thread in the allotted time. This would be hard to do. Multi-threading gives incremental gains, not order-of-magnitude, and so designing a puzzle that could, universally across languages and skill levels, be solved with two threads, but not with one might be impossible. It’s more likely with 4 or even 8 cores, but even then…

  3. #2 revisited… Force the issue. Make the user implement an interface that will be called from multiple threads concurrently, and force them to somehow coalesce the results into a single, coherent output. This approach has the benefit that it could run just as effectively on a single virtual CPU. It has the drawback that it would require a whole new execution and I / O interface, different from all other puzzles. This might be prohibitive across the full spectrum of languages, and should probably be limited to a subset, if implemented.

Thoughts?

  • danBhentschel
3 Likes

For inspiration, see Google’s Distributed Code Jam.

Timings are forced to be interesting there by having the input data be provided by an API instead of standard streams, and taking a noticeable (and provided) amount on time.

Still would be a bit hard to balance with the broad spectrum of languages available here.

2 Likes

Yes, Distributed Code Jam was fun!

Maybe instead of an API specific to each language, we could still use standard streams (or named pipes) to give commands to the referee (for example “READ INPUT X”, “SEND MESSAGE TO Y”, “GET MESSAGE FROM Z”, etc).
The referee could apply timing penalties (like Code Jam) before sending its response to the stream/pipe.