Comment by sedachv | Hacker News Reader

Comment by sedachv | Hacker News Reader

Parent Full thread

StarLisp is basically Common Lisp with parallel-map and parallel-reduce and a special vector data type for them. You can do data-parallel operations over arrays trivially, but it's not clear what array chunk size tradeoff you need for a given problem on today's small core count machines. It might make sense to bring the approach back when there's 100-core machines around; that would basically be a CM-5 on a chip.

In the meantime there's a StarLisp simulator you can play around with: http://sourceforge.net/projects/starsim/

When it comes to data parallelism, StarLisp's successor Paralations (http://www.mactech.com/articles/mactech/Vol.08/08.07/Paralat...) is much more interesting because it deals explicitly with locality. Paralations' successor, NESL (http://www.cs.cmu.edu/~scandal/nesl.html) is implemented on top of Common Lisp, but it's a functional language with ugly syntax.

It would make a lot of sense to have something like StarLisp or APL for CUDA right now. Trying to do data parallelism in C is about the most brain-damaged idea ever. I don't know if anyone is working or interested in that, though.

Overall, I think the MultiLisp (futures) approach is a bigger win for general-purpose parallel programming than StarLisp data parallelism. Doing everything with data-parallel algorithms is hard - you're doing everything with array programming like in APL, but now you need to come up with clever ways to parallelize everything too. But the algorithms themselves are beautiful (read Hillis and Steele's Data Parallel Algorithms, my favorite algorithms paper: http://docs.google.com/viewer?a=v&q=cache:efZTS1nDfBsJ:c...)

> It would make a lot of sense to have something like StarLisp or APL for CUDA right now. Trying to do data parallelism in C is about the most brain-damaged idea ever. I don't know if anyone is working or interested in that, though.

You may well be right, but I challenge you to prove it. I myself am very interested in whether this would work. I have spent many sleepless nights programming GPU algorithms, and wondered if ideas from other programming languages and paradigms (especially functional programming) could be applied to make it easier and more elegant.

The nested data-parallelism approach does look promising on paper, and many people are well aware of the theoretical possibility of this working on GPUs (including people at Nvidia itself), but so far nobody succeeded to make it practical.

So, doing data parallelism in CUDA may be brain-damaged, but the flexibility and performance it delivers is mind-blowing. If you can achieve something comparable using a higher-level functional approach, I will be among your first users, and I'll tell everyone I know.

MultiLisp (AFAIK) is traditional task-parallelism rather than data-parallelism, and would not work well on a GPU.

I'm not talking about data parallelism being bad, but C being a bad data parallel language.

Of course... read my reply again please.

I am not disagreeing with you, I am saying that I would love to see a better data-parallel language than C (or CUDA to be precise), but it does not exist right now (at least not a practical one that would run on a real GPU with reasonable performance and allow non-trivial nested and hierarchical algorithms).

If I remember correctly NESL programs are compiled into vcode a special bytecode that handled vector instructions particularly well. If vcode is ported/specialized to the commodity multicore machines and SSE instruction set, one could profitably run NESL program on contemporary machines. I do not know if there is any such ongoing initiative.

It might be the case that C source for vcode is still available so with a good optimizing compiler one could do the same. It wont quite be the same as a hand optimized assembly implementation of vcode. But perhaps still a satisfactory implementation.

Reply on news.ycombinator.com