Parasitic Computing (2001) [pdf]

by Cieplak • 4 years ago

3 2 4 years ago

Great paper. I remember actually physically printing it off and putting it in a folder when I was in undergrad. I still actually look at it again every few years just because I liked the idea so much.

Cieplak• 4 years ago

First read the paper last week, though heard the concept in 2014 from a colleague who implemented it [1] (for fun I assume).

Recently revisited his little demo interested in the parser design; this time re-reading, the translation between Boolean logic expressions and TCP checksum calculations finally clicked for me.

My current mental model of it is coercing a calculator, which “only” performs addition and subtraction, into evaluating complicated conditional logic expressions. Not sure how a category theorist would describe it; is it an equivalence of two different categories (evaluation of logic expressions/abstract syntax trees) <> (bitwise negation & addition on integer arrays which represent Boolean matrices)?

In a practical engineering sense, I like to think the core concepts illustrate performance optimization principles for representing branching code as branch-free code. I think branching code is likely faster evaluating single expressions, but branch free representations could be useful for SIMD vectorization, e.g., to increase throughput for evaluating a large number or stream of expressions (such as evaluating security policy rules against operating system events).

[1] https://github.com/bninja/parasitology

Parasitic Computing (2001) [pdf]

Related Stories