> The books that are usually recommended seems to be CUDA-centric and out of date.
The CUDA-ones are usually best, because they're at least with a modern API. The other recommendations I got are the 80s stuff on vector computers and the CM-2.
It turns out that a huge community of high-performance programmers have experimented with all of these concepts in the 1970s, 80s, 90s, and 00s, long before GPUs. All of their concepts still work today on modern GPUs.
Looking up the right keywords: such as "CREW-PRAM algorithms" (Concurrent-Read Exclusive Write, Parallel RAM model) immediately gives you plenty of results for some things. (Ex: I just searched on 'CREW-PRAM DFS' and got: https://core.ac.uk/download/pdf/82490222.pdf).
The key is understanding what the "old word" for GPU was. That's PRAM, the Parallel-RAM model. That's how programmers from the 1970s, 1980s, and 1990s talked about algorithms written for the GPU-style called it back then.
Newer articles / books talk about GPUs directly.
--------------
I'd say the fundamentals are covered in the 1970s, such as "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations" by Kogge, which leads to the development of Prefix sum (as it is called today).
Of course, CUDA code is clearer than a theoretical CREW-PRAM discussion. So perhaps its easier if you just read GPU Compute Gems by NVidia to cover the same material. Still, I find that the 1970s writing is often times better written for a beginner (back then, fewer programmers knew how parallel programming worked, but were clearly more math-heavy than today. So I find that reading old articles like that one helps my personal brain and personal thinking pattern)
---------
Ah right, the recommendation. I'd say "Data Parallel Algorithms" by Hillis / Steele (ACM Communications 1986) is an excellent introduction to general-purpose SIMD compute. It was written for CM-2, an ancient supercomputer that no longer exists, but the PRAM style applies to GPU algorithms today.
Its like 15 pages, but it really opens your eyes to the possibilities. A lot of CUDA stuff is very specific to NVidia GPUs (important specific details: like bank conflicts and shared memory, which you absolutely should learn about... but such details should be studied after you learned the way of parallel-thinking / PRAM model / etc. etc.)
This sounds like the article should be against brittle testing.
If any of the following is true then you're writing brittle tests:
- Your test code looks like the code under test
- Your test suite includes examples that tweak one parameter and assert a result
- Your tests pass when you delete an arbitrary line of code from the implementation
I can't imagine shipping any significant project without any tests. How would I know that what I wrote implements my specifications faithfully? Hand waving and trust?
Unit tests are proof by example. They're trivial and don't prove the absence of errors. So I use them sparingly for simple, pure code where a few assumptions are enough.
Property tests are where I spend more of my time and focus. I generate the tests from a specification of a property I want to ensure will hold. It's not a formal proof that there are no errors but if my code survives 500 generated test cases and I have a good distribution over expected and hostile input I can be satisfied that my code is correct.
I don't spend time writing unit tests for effectful code. If I have business logic that is tied up calling a lot of APIs and digging into databases I defunctionalize the effect handling code and write interpreters for the data structures instead so that testing is still pure and easy and the effect handling code is constrained and found in one place. I test the pure version to makes sure the interpreter receives the correct sequence of data.
Sometimes I will use gold tests for serialization code. If I need to make sure that a contract I have with an external system isn't broken by my changes to the code I make sure to run the tests that will check what gets serialized out matches up with the golden examples.
If I need to ensure certain temporal properties hold like resource usage and performance... well I'll need regression and load tests.
These are all a part of the development process. You can ship code with no tests but good luck refactoring, maintaining, fixing, and understanding that code a year from now. It's possible, don't get me wrong, but it takes extreme discipline and even then that sometimes fails. People get tired, leave, get bored, etc. Having the computer check for you that everything is still working as expected is essential in my books.
I personally believe it's the latter. I added arrows indicating opposing incentives at personal level, and I believe the profit motive is much stronger than personal morals, for two main reasons.
One, market competition means you won't survive unless you're optimizing for profits very strongly; with strong enough competition, if your competitor does something shady, you have to follow suit or risk being outcompeted.
Two, professional specialization. I sometimes quip, "the only thing necessary for the triumph of evil is for good men to be separated from it by enough levels of indirection". I mean it. There's plenty of entrepreneurs who wouldn't feel comfortable going to someone personally and lying about their product, or spying on them and selling what they learned to a scammer. But if such entrepreneur hires a marketing manager, who then outsources all marketing to an external agency, which buys its tools off-the-shelf, you may suddenly end up with lies in ads and 50 megabytes of trackers on your GDPR-violating website, and at no point each individual's conscience crosses the "this is EVIL" threshold; everyone can point at each other and say, "I'm just doing what I'm paid to", or "I didn't know my subordinates/subcontractors would do that".
I manually wrote more recursive-descent parsers that I am comfortable to admit (hey, they're fun to write), and most of the "beyond the context-free!" approaches described in this article seem to me to fall into two categories:
1. There is this one common pattern in recursive-descent parsers that allow you to write a more concise recognizing code — let's make it directly expressible! Ordering rules, "not an ending quote/not an end of a comment", "ident that's not a keyword" fall into this category.
2. Semantic actions work really well in practice, but it's gauche. Let's instead encode some restricted, non-Turing-complete, but still useful PL directly in grammar, that'll improve things somehow! Detecting "undeclared identifier used" and "identifier redeclaration" falls into this category: this "quite knotty" Boolean grammar has a dict-like structure threaded through it, isn't it amazing? And this grammar-with-context has built-in support for scoped environments, you don't need your symbol tables anymore (unless you have user-defined types, presumably)!
Of course you can parse the input according using any of these more expressive grammars in the same time and space as you can with a boring old CFG grammar with rule priorities and semantic actions: because that's essentially what they're, just expressed differently. And is there much gained by expressing it differently? It's the same story as with DSLs, really, you keep making them more and more complex and feature-full up until the point you arrive at a full-fledged programming language with awkward semantics and realize that you probably should have stayed with limited DSL that could invoke arbitrary actions written in a proper general-purpose programming languages.
So, yes, "Devising an adequate and convenient formalism on top of grammars with contexts is a challenging task", and it's the task that must be solved before any of those approaches would be more useful than what we have today.
-Do a literature survey and read LOTS of papers. If you are not coming from the standard academic route you are probably vastly underestimating how much existing work has been published. To publish your research you need to place it in the right context, with citations, and really understand what is novel about your ideas. Read lots of papers, take notes, keep track of the bibliographic details. Follow up on citations to find more papers.
-Write up your understanding of the relevant field as a survey of existing literature with citations. This will clarify your thinking and help you become familiar with standard terminology. This will also be part of your finished paper.
-Write up your idea using terminology and notation consistent with your existing survey. Discuss what is novel and different about your idea.
-Analyze your idea from the point of view of other paradigms. Answer possible critiques that would come from other ways of thinking about the same problem. If you've discovered "standard" ways of evaluating your type of idea, do the evaluation to see how you compare.
-Get feedback. Get opinions from as many other people as you can that are as good as you can find. In the draft paper, thank everyone that gives you any feedback. If people give you substantial ideas that improve the work, ask if they want to be co-authors and work with you a bit more.
-Once you feel there is a real research contribution in your paper draft, and people you have shown it to think it is good, start working on getting it published. Put it up on preprint sites and send it to conferences or journals that are relevant. By this point you should know the right venues based on your survey work.
- aider - AI pair programming in your terminal https://aider.chat/
- Tips on coding with GPT (from the author of the above): https://news.ycombinator.com/item?id=36211879
- Cursor - The AI-first Code Editor https://cursor.sh/