shwestrick
Joined 6 years ago
Karma
343
Submissions
53
Member since
Aug 12
Recent submissions
Comment · 1 year ago
Comment · 1 year ago
Worth mentioning that you can always safely switch between AoS and SoA. Either can represent the other; all you've done is transpose the data. The same is not true of AoE/EoA. The AoE [Spam1, Egg1, Spam2, Spam3, Egg2] has no corresponding EoA that can represent it.
What they're actually doing is an AoE => AoEoA transformation: find batches elements with the same tag and reorder the elements so that redundant tags can be eliminated. Essentially, a kind of run-length encoding. It's a nice idea.
Comment · 2 years ago
For those curious, this implementation is based on a recent line of research called "heartbeat scheduling" which amortizes the overheads of creating parallelism, essentially accomplishing a kind of dynamic automatic granularity control.
Related papers:
(2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
(2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
(2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
(2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf
Comment · 2 years ago
Nowadays 210 is actually parallel! You can run 210-style code using MaPLe (https://github.com/MPLLang/mpl) and get competitive performance with respect to C/C++.
If you liked 210, you might also like https://futhark-lang.org/ which is an ML-family language that compiles to GPU with good performance.
Comment · 2 years ago
The two systems have very different tradeoffs.
A few things in particular:
* Separate compilation vs whole-program compilation. OCaml uses separate compilation and therefore has a very constrained heap object model which makes it possible to get polymorphism across separately compiled modules. In contrast, MaPLe uses whole-program compilation and therefore is able to monomorphize and optimize much more aggressively. Whole-program compilation can be slow for large projects.
* The multicore OCaml effort was driven by backwards compatibility, especially in terms of performance -- they wanted to ensure that the performance of existing sequential OCaml code would be completely unaffected by the new run-time system. In contrast, MaPLe focuses on efficiency and scalability for parallel code.
* Multicore OCaml will let you implement your own scheduler, as a library, on top of coarse-grained threads. In contrast, MaPLe comes with a built-in scheduler, and it's not easy to change it.
By the way, there's a recent effort---led by the compiler team at Jane Street---to make it possible to get automatic data unboxing in OCaml! Some more info here: https://www.janestreet.com/tech-talks/unboxed-types-for-ocam...
Comment · 2 years ago
I'm one of the authors of this work -- I can explain a little.
"Provably efficient" means that the language provides worst-case performance guarantees.
For example in the "Automatic Parallelism Management" paper (https://dl.acm.org/doi/10.1145/3632880), we develop a compiler and run-time system that can execute extremely fine-grained parallel code without losing performance. (Concretely, imagine tiny tasks of around only 10-100 instructions each.)
The key idea is to make sure that any task which is *too tiny* is executed sequentially instead of in parallel. To make this happen, we use a scheduler that runs in the background during execution. It is the scheduler's job to decide on-the-fly which tasks should be sequentialized and which tasks should be "promoted" into actual threads that can run in parallel. Intuitively, each promotion incurs a cost, but also exposes parallelism.
In the paper, we present our scheduler and prove a worst-case performance bound. We specifically show that the total overhead of promotion will be at most a small constant factor (e.g., 1% overhead), and also that the theoretical amount of parallelism is unaffected, asymptotically.
All of this is implemented in MaPLe (https://github.com/mpllang/mpl) and you can go play with it now!
Comment · 2 years ago
Enjoyed playing with this!
N-queens search is another nice recursive example. E.g. call this with nqueens(0, 5, [])
function nqueens(i:number, n:number, queens: number[][]) {
if (i >= n) return 1;
let count = 0;
for (let j = 0; j < n; j++) {
let is_threatened = false;
for (let k = 0; k < queens.length; k++) {
let x = queens[k][0];
let y = queens[k][1];
if (i == x || j == y || i - j == x - y || i + j == x + y) {
is_threatened = true;
break;
}
}
if (is_threatened) continue;
count += nqueens(i+1, n, Array(Array(i,j)).concat(queens))
}
return count;
}Comment · 2 years ago
On modern multicore hardware this will be memory-bound; the amount of computation per byte is pretty small (just a few arithmetic instructions on average). My intuition is that the single scan will be faster because it requires a much smaller number of cache misses.
And yes, definitely, the numerical accuracy thing could be a problem. I suspect it wouldn't be too difficult to work around, but I can't say for sure off the top of my head.
Comment · 2 years ago
It's worth noting that you can solve these linear recurrences, `x(t) = a(t)x(t-1) + b(t)`, using a single parallel prefix sum where the elements are the input tuples `(a(t), b(t))`.
The following operator called `combine` works. It's associative over these tuples; the final result will be the final value of the second component. Altogether, this gives you O(n) work and O(log n) span, but using just a single parallel prefix kernel, which may be more efficient in practice.
combine ((a1, b1), (a2, b2)) = (a1 * a2, b1 * a2 + b2)
I'm pretty sure this generalizes, too, to abstract multiplications and additions in any field (at first glance, seems like it should but I haven't done the formal proof yet).
Anyway, it would be interesting to compare this against the solution in the arxiv paper.
----
EDIT: ah, good, this is already being discussed here: https://github.com/glassroom/heinsen_sequence/issues/1
And, for reference, I learned this algorithm from Guy Blelloch; see Sec 1.4.1 of https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
Comment · 3 years ago
Tons and tons of parallel algorithms use prefix sums. Typically the most common use is to compute a collection of offsets in parallel. Some examples:
- compact a hash table (i.e., remove the empty slots)
- flatten a jagged 2D array
- rewrite a dense matrix in compressed-sparse-row (CSR) format
Comment · 3 years ago
Parallelism is only about performance, that's it. If you need something to go faster, parallelism is an option.
Looking into the future, parallelism is one of the only remaining techniques for scaling classical computing. Processors have stopped getting faster. Instead, they're getting fatter (more cores).
Comment · 3 years ago
It's a doctoral degree with a heavy emphasis on pedagogy and teaching. From https://www.cmu.edu/math/grad/phd/index.html:
> The Doctor of Arts degree shares all requirements and standards with the Ph.D., except with regard to the thesis. The D.A. thesis is not expected to display the sort of original research required for a Ph.D. thesis, but rather to demonstrate an ability to organize, understand, and present mathematical ideas in a scholarly way, usually with sufficient innovation and worth to produce a publishable work. Whenever practical, the department provides D.A. candidates with the opportunity to use materials developed to teach a course. While a typical Ph.D. recipient will seek a position that has a substantial research component, the D.A. recipient will usually seek a position where research is not central.
Comment · 3 years ago
More and more people nowadays are programming at high levels of abstraction. If you're designing the frontend of a website, or making a mobile game, or developing a stock trading algorithm, or whatever else, then you probably don't want to constantly worry about details of memory management...
On top of this, GC is necessary for some algorithms. Any data structure with partial sharing (e.g. binary search tree with versioning via path-copying) needs GC to be space-efficient. You could either rely on a built-in GC, or write your own. If you write your own, I think you'll find that it is tedious and error-prone due to memory safety issues.
Comment · 3 years ago
in latex, when typesetting math, by default, parentheses (and other brackets) are always a constant height. So if you put something which is taller than one line in between parentheses, it will look strange, with the content sticking out past the parentheses at the top and/or bottom.
The fix for this (in latex) it to mark pairs of matching parentheses with the macros `\left` and `\right`, (for example: `\left( \frac{x}{y} \right)`) which informs latex that it should figure out how tall the content between the brackets is, and then resize the parentheses appropriately.
Comment · 3 years ago
Some of us are still using SML for research and teaching, e.g. https://github.com/mpllang/mpl
The client who didn't notice a difference would probably call it a bugfix.
The client whose software got ever-so-slightly more reliable probably would call it a minor update.
The client whose software previously was loading large files (luckily) without issue would call it major, because now their software just doesn't work anymore.