“A Deep Dive into an NSO Zero-click IMessage Exploit: Remote Code Execution”, Beer & Groß 2021

“A deep dive into an NSO zero-click iMessage exploit: Remote Code Execution”⁠, Ian Beer, Samuel Groß (2021-12-15; backlinks):

[Project Zero analysis of NSO Group’s FORCEDENTRY zero-click exploit of Apple iOS 13: a “GIF” is sent, which is decoded by the GIF-handling code as a PDF document containing highly-compressed JBIG2 images.

JBIG2 is an old but advanced image compression format, and has some memory bugs allowing a large block of RAM to be written to, providing the initial opening. But how to make that memory useful? It may contain random code, or data, or nothing at all.

The JBIG2 format allows defining variants of a little image by updating it with pixel-level boolean operations: negating, swapping, etc. So the attacker provides 70,000 of these image update commands, which collectively define an entire virtual machine which can do arithmetic etc; this virtual machine then runs an attacker-written program to scan RAM and do stuff.]

…As mentioned above, the substitution based compression output is lossy. After a round of compression and decompression the rendered output doesn’t look exactly like the input. But JBIG2 also supports lossless compression as well as an intermediate “less lossy” compression mode. It does this by also storing (and compressing) the difference between the substituted glyph and each original glyph…Rather than completely encoding the entire difference in one go, it can be done in steps, with each iteration using a logical operator (one of AND, OR, XOR or XNOR) to set, clear or flip bits. Each successive refinement step brings the rendered output closer to the original and this allows a level of control over the “lossiness” of the compression. The implementation of these refinement coding steps is very flexible and they are also able to “read” values already present on the output canvas.

…At this point [in the memory overflow exploit] it would also be possible to write to arbitrary absolute memory addresses if you knew their offsets from the page backing buffer. But how to compute those offsets? Thus far, this exploit has proceeded in a manner very similar to a “canonical” scripting language exploit which in Javascript might end up with an unbounded ArrayBuffer object with access to memory. But in those cases the attacker has the ability to run arbitrary Javascript which can obviously be used to compute offsets and perform arbitrary computations. How do you do that in a single-pass image parser?

My other compression format is Turing-complete! As mentioned earlier, the sequence of steps which implement JBIG2 refinement are very flexible. Refinement steps can reference both the output bitmap and any previously created segments, as well as render output to either the current page or a segment. By carefully crafting the context-dependent part of the refinement decompression, it’s possible to craft sequences of segments where only the refinement combination operators have any effect.

In practice this means it is possible to apply the AND, OR, XOR and XNOR logical operators between memory regions at arbitrary offsets from the current page’s JBIG2Bitmap backing buffer. And since that has been unbounded… it’s possible to perform those logical operations on memory at arbitrary out-of-bounds offsets…It’s when you take this to its most extreme form that things start to get really interesting. What if rather than operating on glyph-sized sub-rectangles you instead operated on single bits?

You can now provide as input a sequence of JBIG2 segment commands which implement a sequence of logical bit operations to apply to the page. And since the page buffer has been unbounded those bit operations can operate on arbitrary memory.

…Practical circuits: JBIG2 doesn’t have scripting capabilities, but when combined with a vulnerability, it does have the ability to emulate circuits of arbitrary logic gates operating on arbitrary memory. So why not just use that to build your own computer architecture and script that‽ That’s exactly what this exploit does. Using over 70,000 segment commands defining logical bit operations, they define a small computer architecture with features such as registers and a full 64-bit adder and comparator which they use to search memory and perform arithmetic operations. It’s not as fast as Javascript, but it’s fundamentally computationally equivalent.

The bootstrapping operations for the sandbox escape exploit are written to run on this logic circuit and the whole thing runs in this weird, emulated environment created out of a single decompression pass through a JBIG2 stream. It’s pretty incredible, and at the same time, pretty terrifying.

“Turing-Universal Learners With Optimal Scaling Laws”, Nakkiran 2021

“Turing-Universal Learners with Optimal Scaling Laws”⁠, Preetum Nakkiran (2021-11-09):

For a given distribution, learning algorithm, and performance metric, the rate of convergence (or data-scaling law) is the asymptotic behavior of the algorithm’s test performance as a function of number of train samples. Many learning methods in both theory and practice have power-law rates, i.e. performance scales as n^−α for some α > 0. Moreover, both theoreticians and practitioners are concerned with improving the rates of their learning algorithms under settings of interest. We observe the existence of a “universal learner”, which achieves the best possible distribution-dependent asymptotic rate among all learning algorithms within a specified runtime (e.g. 𝒪(n²)), while incurring only polylogarithmic slowdown over this runtime. This algorithm is uniform, and does not depend on the distribution, and yet achieves best-possible rates for all distributions. The construction itself is a simple extension of Levin’s universal search (Levin 1973). And much like universal search, the universal learner is not at all practical, and is primarily of theoretical and philosophical interest.

“China Has Already Reached Exascale—On Two Separate Systems”, Hemsoth 2021

“China Has Already Reached Exascale—On Two Separate Systems”⁠, Nicole Hemsoth (2021-10-26; ai /​ ​scaling):

[see also “Why Did China Keep Its Exascale Supercomputers Quiet?”] …The supercomputing community has long been used to public results on the Top 500 list of the world’s most powerful systems with countries actively vying for supremacy. However, with tensions at peak and the entity list haunting the spirit of international competition, we can expect China to remain mum about some dramatic system leaps. Including the fact that the country has already broken the (true/​​LINPACK) exascale barrier in 2021—on more than one machine.

We have it on outstanding authority (under condition of anonymity) that LINPACK was run in March 2021 on the Sunway “Oceanlite” system, which is the follow-on to the #4-ranked Sunway TaihuLight machine. The results yielded 1.3 exaflops peak performance with 1.05 sustained performance in the ideal 35 megawatt power sweet spot.

…The same authority confirmed that a second exascale run in China, this time on the Tianhe-3 system, which we previewed back in May 2019⁠, reached almost identical performance with 1.3 exaflops peak and enough sustained to be functional exascale. We do not have a power figure for this but we were able to confirm this machine is based on the FeiTeng line of processors from Phytium, which is Arm-based with a matrix accelerator. (For clarity, FeiTeng is kind of like “Xeon”, it’s a brand of CPUs from Phytium).

…From what we can tell on these 2 exascale systems there are modest changes to architectures, doubling of chip elements and sockets. That is not to minimize the effort, but we do not suspect new architectures emerging that can fit another coming bit of news, a so-called Futures program that aims to deliver a 20 exaflops supercomputer by 2025, according to our same source, who is based in the United States but in the know about happenings in China.

But here’s something to keep in mind as we go forward in this frigid international climate: perhaps we can no longer expect to have a clear, Top 500 supercomputer list view into national competitiveness in quite the same way. If China, always a contender with the United States, is running LINPACK but not making the results public, what happens to the validity and international importance of that list, which has been a symbol of HPC progress for decades? What does China have to lose, would it not be in the national interest to show off not one, but 2 validated exascale for both peak and sustained results?

Here is something subtle to consider: the forthcoming “Frontier” supercomputer at Oak Ridge National Lab in the U.S. is expected to debut with 1.5 peak exaflops and an expected sustained figure around 1.3 exaflops. Perhaps China has decided to quietly leak that they are first to true exascale without having to publish benchmark results that might show a slightly better performance figure for a US-based machine. Just something to think about.

And here’s another subtle detail. Our source confirms these LINPACK results for both of China’s exascale systems—the first in the world—were achieved in March 2021. When did the entity list appear citing Phytium and Sunway and the centers that host their showboat systems? In April 2021.

“Is This the Simplest (and Most Surprising) Sorting Algorithm Ever?”, Fung 2021

“Is this the simplest (and most surprising) sorting algorithm ever?”⁠, Stanley P. Y. Fung (2021-10-03; math):

We present an extremely simple sorting algorithm. It may look like it is obviously wrong, but we prove that it is in fact correct. We compare it with other simple sorting algorithms [it is a kind of insertion sort], and analyse some of its curious properties.

Algorithm 1: ICan’tBelieveItCanSort (A[1..n]):

  for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] A[j]  

“Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learning”, Rudin et al 2021

“Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learning”⁠, Nikita Rudin, David Hoeller, Philipp Reist, Marco Hutter (2021-09-24; backlinks):

In this work, we present and study a training set-up that achieves fast policy generation for real-world robotic tasks by using massive parallelism on a single workstation GPU. We analyze and discuss the impact of different training algorithm components in the massively parallel regime on the final policy performance and training times. In addition, we present a novel game-inspired curriculum that is well suited for training with thousands of simulated robots in parallel. We evaluate the approach by training the quadrupedal robot ANYmal to walk on challenging terrain. The parallel approach allows training policies for flat terrain in under four minutes, and in twenty minutes for uneven terrain. This represents a speedup of multiple orders of magnitude compared to previous work. Finally, we transfer the policies to the real robot to validate the approach. We open-source our training code to help accelerate further research in the field of learned legged locomotion.

“OpenSquare: Decentralized Repeated Modular Squaring Service”, Aravinda et al 2021

“OpenSquare: Decentralized Repeated Modular Squaring Service”⁠, Sri Aravinda, Krishnan Thyagarajan, Tiantian Gong, Adithya Bhat, Aniket Kate, Dominique Schröder (2021-09-22; backlinks):

Repeated Modular Squaring is a versatile computational operation that has led to practical constructions of timed-cryptographic primitives like time-lock puzzles (TLP) and verifiable delay functions (VDF) that have a fast growing list of applications. While there is a huge interest for timed-cryptographic primitives in the blockchains area, we find 2 real-world concerns that need immediate attention towards their large-scale practical adoption: Firstly, the requirement to constantly perform computations seems unrealistic for most of the users. Secondly, choosing the parameters for the bound T seems complicated due to the lack of heuristics and experience.

We present OpenSquare, a decentralized repeated modular squaring service, that overcomes the above concerns. OpenSquare lets clients outsource their repeated modular squaring computation via smart contracts to any computationally powerful servers that offer computational services for rewards in an unlinkable manner. OpenSquare naturally gives us publicly computable heuristics about a pre-specified number (T) and the corresponding reward amounts of repeated squarings necessary for a time period. Moreover, OpenSquare rewards multiple servers for a single request, in a sybil resistant manner to incentivize maximum server participation and is therefore resistant to censorship and single-points-of failures.

We give game-theoretic analysis to support the mechanism design of OpenSquare: (1) incentivizes servers to stay available with their services, (2) minimizes the cost of outsourcing for the client, and (3) ensures the client receives the valid computational result with high probability. To demonstrate practicality, we also implement OpenSquare’s smart contract in Solidity and report the gas costs for all of its functions.

Our results show that the on-chain computational costs for both the clients and the servers are quite low, and therefore feasible for practical deployments and usage.

[Keywords: cryptographic protocols / time-lock puzzles, repeated modular squaring, smart contracts]

“WarpDrive: Extremely Fast End-to-End Deep Multi-Agent Reinforcement Learning on a GPU”, Lan et al 2021

“WarpDrive: Extremely Fast End-to-End Deep Multi-Agent Reinforcement Learning on a GPU”⁠, Tian Lan, Sunil Srinivasa, Stephan Zheng (2021-08-31; backlinks):

Deep reinforcement learning (RL) is a powerful framework to train decision-making models in complex dynamical environments. However, RL can be slow as it learns through repeated interaction with a simulation of the environment. Accelerating RL requires both algorithmic and engineering innovations. In particular, there are key systems engineering bottlenecks when using RL in complex environments that feature multiple agents or high-dimensional state, observation, or action spaces, for example. We present WarpDrive, a flexible, lightweight, and easy-to-use open-source RL framework that implements end-to-end multi-agent RL on a single GPU (Graphics Processing Unit), building on PyCUDA and PyTorch. Using the extreme parallelization capability of GPUs, WarpDrive enables orders-of-magnitude faster RL compared to common implementations that blend CPU simulations and GPU models. Our design runs simulations and the agents in each simulation in parallel. It eliminates data copying between CPU and GPU. It also uses a single simulation data store on the GPU that is safely updated in-place. Together, this allows the user to run thousands of concurrent multi-agent simulations and train on extremely large batches of experience. For example, WarpDrive yields 2.9 million environment steps/​​second with 2000 environments and 1000 agents (at least 100× higher throughput compared to a CPU implementation) in a benchmark Tag simulation. WarpDrive provides a lightweight Python interface and environment wrappers to simplify usage and promote flexibility and extensions. As such, WarpDrive provides a framework for building high-throughput RL systems.

“Isaac Gym: High Performance GPU-Based Physics Simulation For Robot Learning”, Makoviychuk et al 2021

“Isaac Gym: High Performance GPU-Based Physics Simulation For Robot Learning”⁠, Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, et al (2021-08-24; backlinks):

Isaac Gym offers a high performance learning platform to train policies for wide variety of robotics tasks directly on GPU. Both physics simulation and the neural network policy training reside on GPU and communicate by directly passing data from physics buffers to PyTorch tensors without ever going through any CPU bottlenecks. This leads to blazing fast training times for complex robotics tasks on a single GPU with 1–2 orders of magnitude improvements compared to conventional RL training that uses a CPU based simulator and GPU for neural networks. We host the results and videos at https://sites.google.com/view/isaacgym-nvidia and isaac gym can be download at https://developer.nvidia.com/isaac-gym⁠.

“Megaverse: Simulating Embodied Agents at One Million Experiences per Second”, Petrenko et al 2021

“Megaverse: Simulating Embodied Agents at One Million Experiences per Second”⁠, Aleksei Petrenko, Erik Wijmans, Brennan Shacklett, Vladlen Koltun (2021-07-17; backlinks):

We present Megaverse, a new 3D simulation platform for reinforcement learning and embodied AI research. The efficient design of our engine enables physics-based simulation with high-dimensional egocentric observations at more than 1,000,000 actions per second on a single 8-GPU node. Megaverse is up to 70× faster than DeepMind Lab in fully-shaded 3D scenes with interactive objects. We achieve this high simulation performance by leveraging batched simulation, thereby taking full advantage of the massive parallelism of modern GPUs. We use Megaverse to build a new benchmark that consists of several single-agent and multi-agent tasks covering a variety of cognitive challenges. We evaluate model-free RL on this benchmark to provide baselines and facilitate future research. The source code is available at https:/​​/​​www.megaverse.info

“Brax—A Differentiable Physics Engine for Large Scale Rigid Body Simulation”, Freeman et al 2021

“Brax—A Differentiable Physics Engine for Large Scale Rigid Body Simulation”⁠, C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, Olivier Bachem (2021-06-24; backlinks):

We present Brax, an open source library for rigid body simulation with a focus on performance and parallelism on accelerators, written in JAX. We present results on a suite of tasks inspired by the existing reinforcement learning literature, but remade in our engine. Additionally, we provide reimplementations of PPO⁠, SAC⁠, ES, and direct policy optimization in JAX that compile alongside our environments, allowing the learning algorithm and the environment processing to occur on the same device, and to scale seamlessly on accelerators. Finally, we include notebooks that facilitate training of performant policies on common OpenAI Gym MuJoCo-like tasks in minutes.

“Randomness In Neural Network Training: Characterizing The Impact of Tooling”, Zhuang et al 2021

“Randomness In Neural Network Training: Characterizing The Impact of Tooling”⁠, Donglin Zhuang, Xingyao Zhang, Shuaiwen Leon Song, Sara Hooker (2021-06-22; ai):

The quest for determinism in machine learning has disproportionately focused on characterizing the impact of noise introduced by algorithmic design choices. In this work, we address a less well understood and studied question: how does our choice of tooling introduce randomness to deep neural network training. We conduct large scale experiments across different types of hardware, accelerators, state of art networks, and open-source datasets, to characterize how tooling choices contribute to the level of non-determinism in a system, the impact of said non-determinism, and the cost of eliminating different sources of noise.

Our findings are surprising, and suggest that the impact of non-determinism in nuanced. While top-line metrics such as top-1 accuracy are not noticeably impacted, model performance on certain parts of the data distribution is far more sensitive to the introduction of randomness. Our results suggest that deterministic tooling is critical for AI safety. However, we also find that the cost of ensuring determinism varies dramatically between neural network architectures and hardware types, eg. with overhead up to 746%, 241%, and 196% on a spectrum of widely used GPU accelerator architectures, relative to non-deterministic training. The source code used in this paper is available at Github⁠.

“Cores That Don't Count”, Hochschild et al 2021

2021-hochschild.pdf: “Cores that don't count”⁠, Peter H. Hochschild, Paul Turner, Jeffrey C. Mogul, Rama Govindaraju, Parthasarathy Ranganathan, David E. Culler, et al (2021-05-31):

We are accustomed to thinking of computers as fail-stop, especially the cores that execute instructions, and most system software implicitly relies on that assumption. During most of the VLSI era, processors that passed manufacturing tests and were operated within specifications have insulated us from this fiction. As fabrication pushes towards smaller feature sizes and more elaborate computational structures, and as increasingly specialized instruction-silicon pairings are introduced to improve performance, we have observed ephemeral computational errors that were not detected during manufacturing tests. These defects cannot always be mitigated by techniques such as microcode updates, and may be correlated to specific components within the processor, allowing small code changes to effect large shifts in reliability. Worse, these failures are often “silent”—the only symptom is an erroneous computation.

We refer to a core that develops such behavior as “mercurial.” Mercurial cores are extremely rare, but in a large fleet of servers we can observe the disruption they cause, often enough to see them as a distinct problem—one that will require collaboration between hardware designers, processor vendors, and systems software architects.

This paper is a call-to-action for a new focus in systems research; we speculate about several software-based approaches to mercurial cores, ranging from better detection and isolating mechanisms, to methods for tolerating the silent data corruption they cause.

…Because CEEs may be correlated with specific execution units within a core, they expose us to large risks appearing suddenly and unpredictably for several reasons, including seemingly-minor software changes. Hyperscalers have a responsibility to customers to protect them against such risks. For business reasons, we are unable to reveal exact CEE rates, but we observe on the order of a few mercurial cores per several thousand machines—similar to the rate reported by Facebook [8]⁠. The problem is serious enough for us to have applied many engineer-decades to it.

…We have observed defects scattered across many functions, though there are some general patterns, along with many examples that (so far) seem to be outliers. Failures mostly appear non-deterministically at variable rate. Faulty cores typically fail repeatedly and intermittently, and often get worse with time; we have some evidence that aging is a factor. In a multi-core processor, typically just one core fails, often consistently. CEEs appear to be an industry-wide problem, not specific to any vendor, but the rate is not uniform across CPU products.

Corruption rates vary by many orders of magnitude (given a particular workload or test) across defective cores, and for any given core can be highly dependent on workload and on frequency, voltage, temperature. In just a few cases, we can reproduce the errors deterministically; usually the implementation-level and environmental details have to line up. Data patterns can affect corruption rates, but it’s often hard for us to tell. Some specific examples where we have seen CEE:

• Violations of lock semantics leading to application data corruption and crashes.
• Data corruptions exhibited by various load, store, vector, and coherence operations.
• A deterministic AES miscomputation, which was “self-inverting”: encrypting and decrypting on the same core yielded the identity function, but decryption elsewhere yielded gibberish.
• Corruption affecting garbage collection⁠, in a storage system, causing live data to be lost.
• Database index corruption leading to some queries, depending on which replica (core) serves them, being non-deterministically corrupted.
• Repeated bit-flips in strings, at a particular bit position (which stuck out as unlikely to be coding bugs).
• Corruption of kernel state resulting in process and kernel crashes and application malfunctions.

CEEs are harder to root-cause than software bugs, which we usually assume we can debug by reproducing on a different machine.

“Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”, Johnson 2021

“Intrinsic Propensity for Vulnerability in Computers? Arbitrary Code Execution in the Universal Turing Machine”⁠, Pontus Johnson (2021-04-22; backlinks):

The universal Turing machine is generally considered to be the simplest, most abstract model of a computer. This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky’s 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. The article presents the discovered vulnerability in detail and discusses its potential implications. To the best of our knowledge, an arbitrary code execution vulnerability has not previously been reported for such a simple system.

“Hosting SQLite Databases on Github Pages (or Any Static File Hoster)”, phiresky 2021

“Hosting SQLite databases on Github Pages (or any static file hoster)”⁠, phiresky (2021-04-17):

…if you want to use a database, you either need to write a backend (which you then need to host and maintain forever) or download the whole dataset into the browser (which is not so great when the dataset is more than 10MB).

In the past when I’ve used a backend server for these small side projects at some point some external API goes down or a key expires or I forget about the backend and stop paying for whatever VPS it was on. Then when I revisit it years later, I’m annoyed that it’s gone and curse myself for relying on an external service—or on myself caring over a longer period of time. Hosting a static website is much easier than a “real” server—there’s many free and reliable options (like GitHub, GitLab Pages, Netlify, etc), and it scales to basically infinity without any effort.

So I wrote a tool to be able to use a real SQL database in a statically hosted website!

…As you can see, we can query the wdi_country table while fetching only 1kB of data!…So how do you use a database on a static file hoster? Firstly, SQLite (written in C) is compiled to WebAssembly. SQLite can be compiled with emscripten without any modifications, and the sql.js library is a thin JS wrapper around the wasm code.

sql.js only allows you to create and read from databases that are fully in memory though—so I implemented a virtual file system that fetches chunks of the database with HTTP Range requests when SQLite tries to read from the filesystem: sql.js-httpvfs⁠. From SQLite’s perspective, it just looks like it’s living on a normal computer with an empty filesystem except for a file called /​​wdi.sqlite3 that it can read from. Of course it can’t write to this file, but a read-only database is still useful.

Since fetching data via HTTP has a pretty large overhead, we need to fetch data in chunks and find some balance between the number of requests and the used bandwidth. Thankfully, SQLite already organizes its database in “pages” with a user-defined page size (4 KiB by default). I’ve set the page size to 1 KiB for this database.

…The above query should do 10–20 GET requests, fetching a total of 130–270KiB, depending on if you ran the above demos as well. Note that it only has to do 20 requests and not 270 (as would be expected when fetching 270 KiB with 1 KiB at a time). That’s because I implemented a pre-fetching system that tries to detect access patterns through 3 separate virtual read heads and exponentially increases the request size for sequential reads. This means that index scans or table scans reading more than a few KiB of data will only cause a number of requests that is logarithmic in the total byte length of the scan. You can see the effect of this by looking at the “Access pattern” column in the page read log above.

[ANSIWAVE BBS: an online BBS implemented using this approach.]

“Podracer Architectures for Scalable Reinforcement Learning”, Hessel et al 2021

“Podracer architectures for scalable Reinforcement Learning”⁠, Matteo Hessel, Manuel Kroiss, Aidan Clark, Iurii Kemaev, John Quan, Thomas Keck, Fabio Viola, Hado van Hasselt, et al (2021-04-13; ai /​ ​scaling⁠, reinforcement-learning /​ ​meta-learning⁠,  /​ ​muzero; backlinks):

Supporting state-of-the-art AI research requires balancing rapid prototyping, ease of use, and quick iteration, with the ability to deploy experiments at a scale traditionally associated with production systems. Deep learning frameworks such as TensorFlow, PyTorch and JAX allow users to transparently make use of accelerators, such as TPUs and GPUs, to offload the more computationally intensive parts of training and inference in modern deep learning systems. Popular training pipelines that use these frameworks for deep learning typically focus on (un-)supervised learning. How to best train reinforcement learning (RL) agents at scale is still an active research area.

In this report we argue that TPUs are particularly well suited for training RL agents in a scalable, efficient and reproducible way. Specifically we describe two architectures designed to make the best use of the resources available on a TPU Pod (a special configuration in a Google data center that features multiple TPU devices connected to each other by extremely low latency communication channels).

Anakin: When using small neural networks and grid-world environments an Anakin architecture can easily perform 5 million steps per second, even on the 8-core TPU accessible for free through Google Colab.

This can be very useful to experiment and debug research ideas in the friendly Colab environment. In Figure 4a we show how, thanks to the efficient network connecting different TPU cores in a Pod, performance scales almost linearly with the number of cores; the collective operations used to average gradients across replicas appear to cause only minimal overhead.

In a recent paper by Oh et al 2021 Anakin was used, at a much larger scale, to discover a general reinforcement learning update, from experience of interacting with a rich set of environments implemented in JAX. In this paper, Anakin was used to learn a single shared update rule from 60K JAX environments and 1K policies running and training in parallel.

Despite the complex nature of the system, based on the use of neural networks to meta-learn not just a policy but the entire RL update, Anakin delivered over 3 million steps per second on a 16-core TPU. Training the update rule to a good level of performance, required running Anakin for approximately 24 hours; this would cost approximately $100 on GCP’s preemptible instances

…Sebulba: Our second podracer architecture has also been extensively used for exploring a variety of RL ideas at scale, on environments that cannot be compiled to run on TPU (eg. Atari, DMLab and MuJoCo). As both IMPALA and Sebulba are based on a decomposition between actors and learners, agents designed for the IMPALA architecture can be easily mapped onto Sebulba; for instance a Podracer version of the V-trace agent easily reproduced the results from Espeholt et al 2018. However, we found that training an agent for 200 million frames of an Atari game could be done in just ~1 hour, by running Sebulba on a 8-core TPU. This comes at a cost of approximately $2.88, on GCP’s pre-emptible instances. This is similar in cost to training with the more complex SEED RL framework, and much cheaper than training an agent for 200 million Atari frames using either IMPALA or single-stream GPU-based system such as that traditionally used by DQN⁠.

…In addition to the trajectory length the effective batch size used to compute each update also depends on how many times we replicate the basic 8-TPU setup. Sebulba also scales effectively along this dimension: using 2048 TPU cores (an entire Pod) we were able to further scale all the way to 43 million frames per second, solving the classic Atari videogame Pong in less than 1 minute…Sebulba has also been used to train search-based agents inspired by MuZero (Schrittwieser et al 2020). The workloads associated to these agents are very different from that of model-free agents like IMPALA. The key difference is in the cost of action selection. This increases because MuZero’s policy combines search with deep neural networks (used to guide and/​​or truncate the search). Typically, search-based agents like MuZero required custom C++ implementations of the search to deliver good performance. We could reproduce results from MuZero (no Reanalyse) on multiple RL environments, using Sebulba and a pure JAX implementation of MCTS⁠. Training a MuZero agent with Sebulba for 200M Atari frames takes 9 hours on a 16-core TPU (at a cost of ~$40 on GCP’s preemptible instances).

We found that scalability, via replication, was particularly useful in this context. Figure 4c reports the number of frames per seconds processed by Sebulba when running MuZero on Atari, as a function of the number of TPU cores. The throughput increased linearly with the number of cores.

“Scaling Scaling Laws With Board Games”, Jones 2021

“Scaling Scaling Laws with Board Games”⁠, Andy L. Jones (2021-04-07; ai /​ ​scaling⁠, reinforcement-learning /​ ​alphago⁠,  /​ ​muzero; backlinks):

The largest experiments in machine learning now require resources far beyond the budget of all but a few institutions. Fortunately, it has recently been shown that the results of these huge experiments can often be extrapolated from the results of a sequence of far smaller, cheaper experiments. In this work, we show that not only can the extrapolation be done based on the size of the model, but on the size of the problem as well.

By conducting a sequence of experiments using AlphaZero and Hex⁠, we show that the performance achievable with a fixed amount of compute degrades predictably as the game gets larger and harder. Along with our main result, we further show that the test-time and train-time compute available to an agent can be traded off while maintaining performance.

1. Slope: The slope of the incline is 500 Elo per order of magnitude increase in compute.

   A more memorable interpretation is that if you are in the linearly-increasing regime, then you will need about 2× as much compute as your opponent to beat them 2⁄3 of the time.

2. Perfect play: The minimum compute needed for perfect play increases 7× for each increment in board size.

3. Takeoff: The minimum training compute needed to see any improvement over random play increases by 4× for each increment of board size.

4. Random play: Finally, the distance between random play and perfect play increases by 500 Elo for each increment of board size.

   Unlike the other quantities mentioned previously, the distance between random and perfect play is a property of the game itself rather than of the agent.

…Train-test trade-off: So far we have focused on the compute budget during training, but another pertinent budget is the compute spent during evaluation. All the results discussed previously have used a tree search of size 64 during evaluation, the same as used during training. But there is no reason that the train-time search and test-time search have to be the same size, and so by varying the size of the test-time compute budget we can see in Figure 8 that larger tree searches at test time can substantially improve the performance of an agent.

Knowing now that compute can be spent in 2 places, at train time and test time, the immediate question is: how do these 2 budgets trade off? This is illustrated in Figure 9, which shows that the trade-off is linear in log-compute: for each additional 10× of train-time compute, about 15× of test-time compute can be eliminated, down to a floor of a single-node tree search…the simple relationship between compute at train time and compute at test time was originally surprising to us. Our intuition was that test-time compute is much ‘cheaper’ than train-time compute, and so we were surprised that one could easily substitute for the other. On reflection however, we believe the key distinction is that an optimization at test-time needs only optimise over one sample, while train-time compute meanwhile must optimise over the entire distribution of samples.

…the way in which performance scales with compute is that an agent with twice as much compute as its opponent can win roughly 2⁄3 of the time. This behaviour is strikingly similar to that of a toy model where each player chooses as many random numbers as they have compute, and the player with the highest number wins³. In this toy model, doubling your compute doubles how many random numbers you draw, and the probability that you possess the largest number is 2⁄3 [as you go from 1:1, half the total numbers drawn, to 2:1, or 2/​​(2+1)—as if each tree search were an independent lottery ticket]. This suggests that the complex game play of Hex might actually reduce to each agent having a ‘pool’ of strategies proportional to its compute, and whoever picks the better strategy wins. While on the basis of the evidence presented herein we can only consider this to be serendipity, we are keen to see whether the same behaviour holds in other games.

Second, both the relation of performance to board size and the relation of performance to compute are smooth. Before embarking on this project, a key unknown was whether performance would show any ‘spikes’ with regards to compute or board size. A spike with regards to compute might indicate the model had achieved some key insight, while a spike with regards to board size might indicate a minimum complexity past which key insights are available for the model to discover. As is however, models’ performance changes smoothly and predictably with both increased compute and increased complexity.

“Why Are Tar.xz Files 15× Smaller When Using Python''s Tar Library Compared to MacOS Tar?”, Lindestøkke 2021

“Why are tar.xz files 15× smaller when using Python''s tar library compared to macOS tar?”⁠, Saaru Lindestøkke (2021-03-15; backlinks):

I’m compressing ~1.3 GB folders each filled with 1440 JSON files and find that there’s a 15-fold difference between using the tar command on macOS or Raspbian 10 (Buster) and using Python’s built-in tarfile library…The output is:

• zsh tar filesize: 23.7 MB
• py tar filesize: 1.49 MB

…The zsh archive uses an unknown order, and the Python archive orders the file by modification date. I am not sure if that matters…EDIT: Ok, I think I found the issue: BSD tar and GNU tar without any sort options put the files in the archive in an undefined order… I think the reason sorting has such an impact is as follows:

My JSON files contain measurements from hundreds of sensors. Every minute I read out all sensors, but only a few of these sensors have a different value from minute to minute. By sorting the files by name (which has the creation Unix time at the beginning of it), two subsequent files have very little different characters between them. Apparently this is very favourable for the compression efficiency.

“Large Batch Simulation for Deep Reinforcement Learning”, Shacklett et al 2021

“Large Batch Simulation for Deep Reinforcement Learning”⁠, Brennan Shacklett, Erik Wijmans, Aleksei Petrenko, Manolis Savva, Dhruv Batra, Vladlen Koltun, Kayvon Fatahalian, et al (2021-03-12; backlinks):

We accelerate deep reinforcement learning-based training in visually complex 3D environments by two orders of magnitude over prior work, realizing end-to-end training speeds of over 19,000 frames of experience per second on a single GPU and up to 72,000 frames per second on a single 8-GPU machine.

The key idea of our approach is to design a 3D renderer and embodied navigation simulator around the principle of “batch simulation”: accepting and executing large batches of requests simultaneously. Beyond exposing large amounts of work at once, batch simulation allows implementations to amortize in-memory storage of scene assets, rendering work, data loading, and synchronization costs across many simulation requests, dramatically improving the number of simulated agents per GPU and overall simulation throughput.

To balance DNN inference and training costs with faster simulation, we also build a computationally efficient policy DNN that maintains high task performance, and modify training algorithms to maintain sample efficiency when training with large mini-batches.

By combining batch simulation and DNN performance optimizations, we demonstrate that PointGoal navigation agents can be trained in complex 3D environments on a single GPU in 1.5 days to 97% of the accuracy of agents trained on a prior state-of-the-art system using a 64-GPU cluster over 3 days. We provide open-source reference implementations of our batch 3D renderer and simulator to facilitate incorporation of these ideas into RL systems.

“Pretrained Transformers As Universal Computation Engines”, Lu et al 2021

“Pretrained Transformers as Universal Computation Engines”⁠, Kevin Lu, Aditya Grover, Pieter Abbeel, Igor Mordatch (2021-03-09; ai /​ ​scaling; backlinks):

We investigate the capability of a transformer pretrained on natural language to generalize to other modalities with minimal finetuning—in particular, without finetuning of the self-attention and feedforward layers of the residual blocks. We consider such a model, which we call a Frozen Pretrained Transformer (FPT), and study finetuning it on a variety of sequence classification tasks spanning numerical computation, vision, and protein fold prediction. In contrast to prior works which investigate finetuning on the same modality as the pretraining dataset, we show that pretraining on natural language can improve performance and compute efficiency on non-language downstream tasks. Additionally, we perform an analysis of the architecture, comparing the performance of a random initialized transformer to a random LSTM⁠. Combining the two insights, we find language-pretrained transformers can obtain strong performance on a variety of non-language tasks.

“Entropy Trade-offs in Artistic Design: A Case Study of Tamil kolam”, Tran et al 2021

“Entropy trade-offs in artistic design: A case study of Tamil kolam”⁠, N.-Han Tran, Timothy Waring, Silke Atmaca, Bret A. Beheim (2021-03-01; design⁠, psychology /​ ​novelty):

From an evolutionary perspective, art presents many puzzles. Humans invest substantial effort in generating apparently useless displays that include artworks. These vary greatly from ordinary to intricate. From the perspective of signalling theory, these investments in highly complex artistic designs can reflect information about individuals and their social standing.

Using a large corpus of kolam art from South India (n = 3,139 kolam from 192 women), we test a number of hypotheses about the ways in which social stratification and individual differences affect the complexity of artistic designs.

Consistent with evolutionary signalling theories of constrained optimisation, we find that kolam art tends to occupy a ‘sweet spot’ at which artistic complexity, as measured by Shannon information entropy⁠, remains relatively constant from small to large drawings. This stability is maintained through an observable, apparently unconscious trade-off between 2 standard information-theoretic measures: richness and evenness⁠.

Although these drawings arise in a highly stratified, caste-based society, we do not find strong evidence that artistic complexity is influenced by the caste boundaries of Indian society. Rather, the trade-off is likely due to individual-level aesthetic preferences and differences in skill, dedication and time, as well as the fundamental constraints of human cognition and memory.

[Keywords: art, signalling, entropy⁠, skill, material culture, Bayesian inference]

…Kolam drawings are geometric art practised by women in the Kodaikanal region of Tamil Nadu⁠, southern India (Layard 1937). A kolam consists of one or more loops drawn around a grid of dots (in Tamil called pulli). On a typical morning, a Tamil woman will prepare a grid of dots on the threshold of her home, and then draw a kolam with rice powder or chalk. During the day the drawing weathers away, and a new kolam is created the next day. Kolam drawings are historically traditions of matrilines, but more recently are also a topic of cultural education in Tamil schools. Girls in Tamil Nadu begin practising kolam-making from an early age, and competency in this art is considered necessary for the transition into womanhood (Nagarajan 2018, Feeding a thousand souls: Women, ritual, and ecology in India—An exploration of the kolam). Although the primary medium is the threshold of the home, women practice kolam-making in notebooks, and it is common for artists to share, copy and embellish each other’s kolam designs. Such unrestrained artistic exchange is fostered by the fact that kolam designs are not considered to belong to any one person, but rather to be a type of community knowledge (Nagarajan 2018). However, the ability to successfully draw aesthetically pleasing (ie. diverse, complex, large) kolam drawings is said to reflect certain qualities of a woman (eg. her degree of traditionalness or patience), and as such her capacity to run a household and become a good wife and mother (Laine 2013; Nagarajan 2018).

…Here we study the ner pulli nelevu or sikku kolam family because of its unique form. Because sikku kolam drawings represent an unusually strict system of artistic expression, kolam drawings can be mapped onto a small identifiable set of gestures and are therefore well suited to systematic, quantitative analyses as a naturalistic model system of cultural evolution. A given kolam’s gesture sequence can be characterised by a number of informative summary statistics which capture aspects of kolam itself: the sequence length (ie. the total number of gestures), the discrete canvas size (measured by the grid of dots, or pulli), the gesture density per unit canvas area and gesture diversity as measured by evenness (here, the Gini index), richness and Shannon information entropy.

“Warehouse-Scale Video Acceleration: Co-design and Deployment in the Wild”, Ranganathan et al 2021

2021-ranganathan.pdf#google: “Warehouse-Scale Video Acceleration: Co-design and Deployment in the Wild”⁠, Parthasarathy Ranganathan, Daniel Stodolsky, Jeff Calow, Jeremy Dorfman, Marisabel Guevara, Clinton Wills Smullen IV, et al (2021-02-27; backlinks):

Video sharing (eg. YouTube, Vimeo, Facebook, TikTok) accounts for the majority of internet traffic, and video processing is also foundational to several other key workloads (video conferencing, virtual/​​augmented reality, cloud gaming, video in Internet-of-Things devices, etc.). The importance of these workloads motivates larger video processing infrastructures and—with the slowing of Moore’s law—specialized hardware accelerators to deliver more computing at higher efficiencies.

This paper describes the design and deployment, at scale, of a new accelerator targeted at warehouse-scale video transcoding. We present our hardware design including a new accelerator building block—the video coding unit (VCU)—and discuss key design trade-offs for balanced systems at data center scale and co-designing accelerators with large-scale distributed software systems. We evaluate these accelerators “in the wild” serving live data center jobs, demonstrating 20–33× improved efficiency over our prior well-tuned non-accelerated baseline. Our design also enables effective adaptation to changing bottlenecks and improved failure management, and new workload capabilities not otherwise possible with prior systems.

To the best of our knowledge, this is the first work to discuss video acceleration at scale in large warehouse-scale environments.

[Keywords: video transcoding, warehouse-scale computing, domain-specific accelerators, hardware-software co-design]

---

The VCU package is a full-length PCI-E card and looks a lot like a graphics card. A board has 2 Argos ASIC chips buried under a gigantic, passively cooled aluminum heat sink. There’s even what looks like an 8-pin power connector on the end because PCI-E just isn’t enough power.

Google provided a lovely chip diagram that lists 10 “encoder cores” on each chip, with Google’s white paper adding that “all other elements are off-the-shelf IP blocks.” Google says that “each encoder core can encode 2160p in realtime, up to 60 FPS (frames per second) using 3 reference frames.”

The cards are specifically designed to slot into Google’s warehouse-scale computing system. Each compute cluster in YouTube’s system will house a section of dedicated “VCU machines” loaded with the new cards, saving Google from having to crack open every server and load it with a new card. Google says the cards resemble GPUs because they are what fit in its existing accelerator trays. CNET reports that “thousands of the chips are running in Google data centers right now”, and thanks to the cards, individual video workloads like 4K video “can be available to watch in hours instead of the days it previously took.”

Factoring in the research and development on the chips, Google says this VCU plan will save the company a ton of money, even given the below benchmark showing the TCO (total cost of ownership) of the setup compared to running its algorithm on Intel Skylake chips and Nvidia T4 Tensor core GPUs.

“NNUE: The Neural Network of the Stockfish Chess Engine”, Goucher 2021

“NNUE: The neural network of the Stockfish chess engine”⁠, Adam P. Goucher (2021-01-08; reinforcement-learning):

The real cleverness of Stockfish’s neural network is that it’s an efficiently-updatable neural network (NNUE). Specifically, it’s a simple feedforward network with:

• a large (10.5M parameters!) input layer, illustrated below, that can utilise two different levels of sparsity for computational efficiency;
• three much smaller layers (with 17.5k parameters in total) which are evaluated densely using vector instructions;
• a single scalar output to give a numerical score for the position, indicating how favourable it is for the player about to move.

Everything is done using integer arithmetic, with 16-bit weights in the first layer and 8-bit weights in the remaining layers…The inputs to the layer are two sparse binary arrays, each consisting of 41,024 elements. It may seem highly redundant to encode a chess position using 82,048 binary features, but this is similar to an approach (called ‘feature crosses’) used in recommender systems.

…There are two levels of sparsity which are utilised when computing this affine transformation from ℝ^41,024 to ℝ²⁵⁶, allowing the network to be efficiently evaluated many times in a tree search:

• the 41,024-element implicit vectors are themselves sparse: the number of nonzero elements is equal to the number of non-king pieces on the board.
• moving a piece typically changes very few of the entries of the vector: if it’s a regular non-king move, only 2 entries change; if it’s a non-king move with capture, then 3 entries change.

It’s this second aspect which warrants the name ‘efficiently updatable’: when a move is made (or unmade, since we’re doing a tree search), we only need to add/​​subtract a few 256-element matrix columns from the resulting ‘dense worldview’ to update it.

Unless a king is moved, this (2 or 3 vector additions/​​subtractions) beats summing all of the matrix columns corresponding to nonzero entries (up to 30 vector additions), which in turn unconditionally beats doing a regular dense matrix-vector multiplication (41,024 vector additions). That is to say, the second-level sparsity is about 10× more efficient than the first-level sparsity, which is in turn about 1000× more efficient than naively doing a dense matrix-vector multiplication.

“The Semiconductor Supply Chain: Assessing National Competitiveness”, Khan et al 2021

2021-khan.pdf: “The Semiconductor Supply Chain: Assessing National Competitiveness”⁠, Saif M. Khan, Alexander Mann, Dahlia Peterson (2021-01; economics; backlinks):

[Summary by Mark Xu:

This report analyzes the current supply chain for semiconductors. It particularly focuses on which portions of the supply chain are controlled by US and its allies and China. Some key insights:

• The US semiconductor industry is estimated to contribute 39% of the total value of the global semiconductor supply chain.
• The semiconductor supply chain is incredibly complicated. The production of a single chip requires more than 1,000 steps and passes through borders more than 70 times throughout production.
• AMD is currently the only company with expertise in designing both high-end GPUs and high-end CPUs.
• TSMC controls 54% of the logic foundry market, with a larger share for leading edge production, eg. state-of-the-art 5 nm node chips.
• Revenue per wafer for TSMC is rapidly increasing, while other foundries are seeing declines.
• The Netherlands has a monopoly on extreme ultraviolet (EUV) scanners, equipment needed to make the most advanced chips.
• The Netherlands and Japan have a monopoly on argon fluoride (ArF) immersion scanners, needed to make the second most advanced chips.
• The US has a monopoly on full-spectrum electronic design automation (EDA) software needed to design semiconductors.
• Japan, Taiwan, Germany and South Korea manufacture the state-of-the-art 300 mm wafers used for 99.7% of the world’s chip manufacturing. This manufacturing process requires large amounts of tacit know-how.
• China controls the largest share of manufacturing for most natural materials. The US and its allies have a sizable share in all materials except for low-grade gallium, tungsten and magnesium.
• China controls ~2⁄3^rds of the world’s silicon production, but the US and allies have reserves.

The report also analyzes US competitiveness at detailed levels of the supply chain, which I didn’t read that carefully. Tables:]

“Scaling down Deep Learning”, Greydanus 2020

“Scaling down Deep Learning”⁠, Sam Greydanus (2020-12-01; ai /​ ​sparsity⁠, reinforcement-learning /​ ​meta-learning; backlinks):

…Yet in spite of its historical importance, MNIST has three notable shortcomings. First, it does a poor job of differentiating between linear, nonlinear, and translation-invariant models. For example, logistic, MLP, and CNN benchmarks obtain 94, 99+, and 99+% accuracy on it. This makes it hard to measure the contribution of a CNN’s spatial priors or to judge the relative effectiveness of different regularization schemes. Second, it is somewhat large for a toy dataset. Each input example is a 784-dimensional vector and thus it takes a non-trivial amount of computation to perform hyperparameter searches or debug a meta-learning loop. Third, MNIST is hard to hack. The ideal toy dataset should be procedurally generated so that researchers can smoothly vary parameters such as background noise, translation, and resolution.

In order to address these shortcomings, we propose the MNIST-1D dataset. It is a minimalist, low-memory, and low-compute alternative to MNIST, designed for exploratory deep learning research where rapid iteration is a priority. Training examples are 20× smaller but they are still better at measuring the difference between (1) linear and nonlinear classifiers and (2) models with and without spatial inductive biases (eg. translation invariance). The dataset is procedurally generated but still permits analogies to real-world digit classification…Unlike MNIST, each example is a one-dimensional sequence of points. To generate an example, we begin with a digit template and then randomly pad, translate, and transform it.

Example use cases: In this section we will explore several examples of how MNIST-1D can be used to study core “science of deep learning” phenomena.

1. Finding lottery tickets…Unlike many follow-up experiments on the lottery ticket, this one took just two days of researcher time to produce. The curious reader can also reproduce these results in their browser in a few minutes.

2. Observing deep double descent…We see the MNIST-1D dataset as a good tool for exploring these properties. In fact, we were able to reproduce the double descent pattern after a few hours of researcher effort. The figure below shows our results for a fully-connected network and a convolutional model.

3. Gradient-based meta-learning…A model does this by having two levels of optimization: the first is a fast inner loop which corresponds to a traditional learning objective and second is a slow outer loop which updates the “meta” properties of the learning process…Meta-learning is a promising topic but it is very difficult to scale. First of all, meta-learning algorithms consume enormous amounts of time and compute. Second of all, implementations tend to grow complex since there are twice as many hyperparameters (one set for each level of optimization) and most deep learning frameworks are not set up well for meta-learning. This places an especially high incentive on debugging and iterating meta-learning algorithms on small-scale datasets such as MNIST-1D. For example, it took just a few hours to implement and debug the gradient-based hyperparameter optimization of a learning rate shown below.

   • Meta-learning an activation function: Having implemented a “minimal working example” of gradient-based meta-learning, we realized that it permitted a simple and novel extension: meta-learning an activation function. With a few more hours of researcher time, we were able to parameterize our classifier’s activation function with a second neural network and then learn the weights using meta-gradients.

4. Measuring the spatial priors of deep networks: …Principle among these priors is the translation invariance of convolution. A primary motivation for this dataset was to construct a toy problem that could effectively quantify a model’s spatial priors. The second figure in this post illustrates that this is indeed possible with MNIST-1D.

5. Benchmarking pooling methods. Our final case study begins with a specific question: What is the relationship between pooling and sample efficiency? We had not seen evidence that pooling makes models more or less sample efficient, but this seemed an important relationship to understand. With this in mind, we trained models with different pooling methods and training set sizes and found that, while pooling tended to be effective in low-data regimes, it did not make much of a difference in high-data regimes.

…this post argues in favor of small-scale machine learning research. Neural networks do not have problems with scaling or performance—but they do have problems with interpretability, reproducibility, and iteration speed. We see carefully-controlled, small-scale experiments as a great way to address these problems…For example, several of the findings reported in this post are at the point where they should be investigated at scale. We would like to show that large scale lottery tickets also learn spatial inductive biases, and show evidence that they develop local connectivity. We would also like to try meta-learning an activation function on a larger model in the hopes of finding an activation that will outperform ReLU and Swish in generality. We should emphasize that we are only ready to scale these results now that we have isolated and understood them in a controlled setting. We believe that scaling a system is only a good idea once the relevant causal mechanisms have been isolated and understood. [cf scaling law papers] …Our work also bears philosophical similarities to the “Synthetic Petri Dish” by Rawal et al 2020⁠.

Closing Thoughts: There is a counterintuitive possibility that in order to explore the limits of how large we can scale neural networks, we may need to explore the limits of how small we can scale them first. Scaling models and datasets downward in a way that preserves the nuances of their behaviors at scale will allow researchers to iterate quickly on fundamental and creative ideas. This fast iteration cycle is the best way of obtaining insights about how to incorporate progressively more complex inductive biases into our models. We can then transfer these inductive biases across spatial scales in order to dramatically improve the sample efficiency and generalization properties of large-scale models. We see the humble MNIST-1D dataset as a first step in that direction.

“I Know What You Bought At Chipotle for $9.81 by Solving A Linear Inverse Problem”, Fleder & Shah 2020

2020-fleder.pdf: “I Know What You Bought At Chipotle for $9.81 by Solving A Linear Inverse Problem”⁠, Michael Fleder, Devavrat Shah (2020-12-01):

We consider the question of identifying which set of products are purchased and at what prices in a given transaction by observing only the total amount spent in the transaction, and nothing more. The ability to solve such an inverse problem can lead to refined information about consumer spending by simply observing anonymized credit card transactions data.

Indeed, when considered in isolation, it is impossible to identify the products purchased and their prices from a given transaction just based on the transaction total. However, given a large number of transactions, there may be a hope. As the main contribution of this work, we provide a robust estimation algorithm for decomposing transaction totals into the underlying, individual product(s) purchased by utilizing a large corpus of transactions.

Our method recovers a (product prices) vector p ∈ ℝ[^*N*^~\>0~]{.supsub} of unknown dimension (number of products) N as well as matrix A ∈ ℤ[^*M*×*N*^~≥0~]{.supsub} simply from M observations (transaction totals) y ∈ ℝ[^*M*^~\>0~]{.supsub} such that y = Ap + η with η ∈ ℝ^M representing noise (taxes, discounts, etc). We formally establish that our algorithm identifies N, A precisely and p approximately, as long as each product is purchased individually at least once, ie. M ≥ N and A has rank N. Computationally, the algorithm runs in polynomial time (with respect to problem parameters), and thus we provide a computationally efficient and statistically robust method for solving such inverse problems.

We apply the algorithm to a large corpus of anonymized consumer credit card transactions in the period 2016–2019, with data obtained from a commercial data vendor. The transactions are associated with spending at Apple, Chipotle, Netflix, and Spotify. From just transactions data, our algorithm identifies (1) key price points (without access to the listed prices), (2) products purchased within a transaction, (3) product launches, and (4) evidence of a new ‘secret’ product from Netflix—rumored to be in limited release.

[Keywords: blind compressed sensing; alternative data; finance; consumer credit card transactions]

“Inductive Biases for Deep Learning of Higher-Level Cognition”, Goyal & Bengio 2020

“Inductive Biases for Deep Learning of Higher-Level Cognition”⁠, Anirudh Goyal, Yoshua Bengio (2020-11-30; backlinks):

A fascinating hypothesis is that human and animal intelligence could be explained by a few principles (rather than an encyclopedic list of heuristics). If that hypothesis was correct, we could more easily both understand our own intelligence and build intelligent machines. Just like in physics, the principles themselves would not be sufficient to predict the behavior of complex systems like brains, and substantial computation might be needed to simulate human-like intelligence. This hypothesis would suggest that studying the kind of inductive biases that humans and animals exploit could help both clarify these principles and provide inspiration for AI research and neuroscience theories. Deep learning already exploits several key inductive biases, and this work considers a larger list, focusing on those which concern mostly higher-level and sequential conscious processing. The objective of clarifying these particular principles is that they could potentially help us build AI systems benefiting from humans’ abilities in terms of flexible out-of-distribution and systematic generalization, which is currently an area where a large gap exists between state-of-the-art machine learning and human intelligence.

“Verifiable Timed Signatures Made Practical”, Thyagarajan et al 2020

2020-thyagarajan.pdf: “Verifiable Timed Signatures Made Practical”⁠, Sri Aravinda Krishnan Thyagarajan, Adithya Bhat, Giulio Malavolta, Nico Döttling, Aniket Kate, Dominique Schröder, et al (2020-10-01; backlinks):

A verifiable timed signature (VTS) scheme allows one to time-lock a signature on a known message for a given amount of time T such that after performing a sequential computation for time T anyone can extract the signature from the time-lock. Verifiability ensures that anyone can publicly check if a time-lock contains a valid signature on the message without solving it first, and that the signature can be obtained by solving the same for time T.

This work formalizes VTS, presents efficient constructions compatible with BLS, Schnorr, and ECDSA signatures, and experimentally demonstrates that these constructions can be employed in practice. On a technical level, we design an efficient cut-and-choose protocol based on the homomorphic time-lock puzzles to prove the validity of a signature encapsulated in a time-lock puzzle. We also present a new efficient range proof protocol that substantially improves upon existing proposals in terms of the proof size, and is also of independent interest.

While VTS is a versatile tool with numerous existing applications, we demonstrate VTS’s applicability to resolve three novel challenging issues in the space of cryptocurrencies. Specifically, we show how VTS is the cryptographic cornerstone to construct: (1) Payment channel networks with improved on-chain unlinkability of users involved in a transaction, (2) multi-party signing of transactions for cryptocurrencies without any on-chain notion of time and (3) cryptocurrency-enabled fair multi-party computation protocol.

[Keywords: timed signatures, time lock puzzles, payment channel network, multi-party signing]

“Engineering In-place (Shared-memory) Sorting Algorithms”, Axtmann et al 2020

“Engineering In-place (Shared-memory) Sorting Algorithms”⁠, Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders (2020-09-28; backlinks):

We present sorting algorithms that represent the fastest known techniques for a wide range of input sizes, input distributions, data types, and machines. A part of the speed advantage is due to the feature to work in-place. Previously, the in-place feature often implied performance penalties. Our main algorithmic contribution is a blockwise approach to in-place data distribution that is provably cache-efficient. We also parallelize this approach taking dynamic load balancing and memory locality into account. Our comparison-based algorithm, In-place Superscalar Samplesort (IPS⁴o), combines this technique with branchless decision trees. By taking cases with many equal elements into account and by adapting the distribution degree dynamically, we obtain a highly robust algorithm that outperforms the best in-place parallel comparison-based competitor by almost a factor of three. IPS⁴o also outperforms the best comparison-based competitors in the in-place or not in-place, parallel or sequential settings. IPS⁴o even outperforms the best integer sorting algorithms in a wide range of situations. In many of the remaining cases (often involving near-uniform input distributions, small keys, or a sequential setting), our new in-place radix sorter turns out to be the best algorithm. Claims to have the, in some sense, “best” sorting algorithm can be found in many papers which cannot all be true. Therefore, we base our conclusions on extensive experiments involving a large part of the cross product of 21 state-of-the-art sorting codes, 6 data types, 10 input distributions, 4 machines, 4 memory allocation strategies, and input sizes varying over 7 orders of magnitude. This confirms the robust performance of our algorithms while revealing major performance problems in many competitors outside the concrete set of measurements reported in the associated publications.

“"Less Than One"-Shot Learning: Learning N Classes From M<N Samples”, Sucholutsky & Schonlau 2020

“"Less Than One"-Shot Learning: Learning N Classes From M<N Samples”⁠, Ilia Sucholutsky, Matthias Schonlau (2020-09-17; backlinks):

Deep neural networks require large training sets but suffer from high computational cost and long training times. Training on much smaller training sets while maintaining nearly the same accuracy would be very beneficial. In the few-shot learning setting, a model must learn a new class given only a small number of samples from that class. One-shot learning is an extreme form of few-shot learning where the model must learn a new class from a single example. We propose the ‘less than one’-shot learning task where models must learn N new classes given only M<N examples and we show that this is achievable with the help of soft labels. We use a soft-label generalization of the k-Nearest Neighbors classifier to explore the intricate decision landscapes that can be created in the ‘less than one’-shot learning setting. We analyze these decision landscapes to derive theoretical lower bounds for separating N classes using M<N soft-label samples and investigate the robustness of the resulting systems.

“An RNA-Based Theory of Natural Universal Computation”, Akhlaghpour 2020

“An RNA-Based Theory of Natural Universal Computation”⁠, Hessameddin Akhlaghpour (2020-08-20; backlinks):

Life is confronted with computation problems in a variety of domains including animal behavior, single-cell behavior, and embryonic development. Yet we currently have no biologically plausible model capable of universal computation, i.e., Turing-equivalent in scope. Network models (which include neural networks, intracellular signaling cascades, and gene regulatory networks) fall short of universal computation, but are assumed to be capable of explaining cognition and development. I present a class of models that bridge two concepts from distant fields: combinatory logic (or, equivalently, lambda calculus) and molecular biology. A set of basic RNA editing rules can make it possible to compute any computable function with identical algorithmic complexity to that of Turing machines. The models do not assume extraordinarily complex molecular machinery or any processes that radically differ from what we already know to occur in cells. Distinct independent enzymes can mediate each of the rules and RNA molecules solve the problem of parenthesis matching through their secondary structure. The most plausible of these models does not strictly mimic the operation rules of combinatory logic or lambda calculus; it relies on standard RNA transcription from static genomic templates and the editing rules can be implemented with merely cleavage and ligation operations. This demonstrates that universal computation is well within the reach of molecular biology. It is therefore reasonable to assume that life has evolved—or possibly began with—a universal computer that yet remains to be discovered. The variety of seemingly unrelated computational problems across many scales can potentially be solved using the same RNA-based computation system. Experimental validation of this theory may immensely impact our understanding of memory, cognition, development, disease, evolution, and the early stages of life.

“Measuring Hardware Overhang”, hippke 2020

“Measuring hardware overhang”⁠, hippke (2020-08-05; ai /​ ​scaling⁠, economics /​ ​experience-curve; backlinks):

How can we measure a potential AI or hardware overhang? For the problem of chess, modern algorithms gained two orders of magnitude in compute (or ten years in time) compared to older versions. While it took the supercomputer “Deep Blue” to win over world champion Gary Kasparov in 1997, today’s Stockfish program achieves the same ELO level on a 486-DX4-100 MHz from 1994. In contrast, the scaling of neural network chess algorithms to slower hardware is worse (and more difficult to implement) compared to classical algorithms. Similarly, future algorithms will likely be able to better leverage today’s hardware by 2–3 orders of magnitude. I would be interested in extending this scaling relation to AI problems other than chess to check its universality.

…We may wonder: How do modern (better) chess algorithms perform on slower hardware? I tested this with Stockfish version 8 (SF8), one of the strongest classical chess engine. I simulated 10k matches of SF8 against slower versions of itself and a series of older engines for calibration⁠, using cutechess-cli. In these benchmarks, I varied the total number of nodes to be searched during each game. I kept the RAM constant (this may be unrealistic for very old machines, see below). By assuming a fixed thinking time per game, the experiments scale out to slower machines. By cross-correlating various old benchmarks of Stockfish and other engines on older machines, I matched these ratings to units of MIPS; and finally, MIPS approximately to the calendar year. Depending on the actual release dates of the processors, the year axis has a jitter up to 2 years. I estimate the error for the compute estimates to be perhaps 20%, and certainly less than 50%. As we will see, the results measure in orders of magnitude, so that these errors are small in comparison (<10%).

Results: SF8 achieves Kasparov’s 2850 ELOs running on a 486-100 MHz introduced in 1994, three years before the Kasparov-Deep Blue match. These ELOs refer to tournament conditions as in the 1997 IBM games. In other words, with today’s algorithms, computers would have beat the world chess champion already in 1994 on a contemporary desk computer (not a supercomputer). [Followup: “A closer look at chess scalings (into the past)”>⁠/​​“Benchmarking an old chess engine on new hardware”: “How much more compute does Stockfish 3 require to match Stockfish 13? Answer: 32× (uncertainty: 30–35×)…Interpretation: If we accept SF as amongst the very best chess programs in the last decade, we can make a more general assessment of chess compute vs. algorithm. Compute explains 30–50% of the computer chess ELO progress; algorithm improvements explain 50–70%.”]

“A Time Leap Challenge for SAT Solving”, Fichte et al 2020

“A Time Leap Challenge for SAT Solving”⁠, Johannes K. Fichte, Markus Hecher, Stefan Szeider (2020-08-05; ai⁠, economics /​ ​experience-curve; backlinks):

We compare the impact of hardware advancement and algorithm advancement for SAT solving over the last two decades. In particular, we compare 20-year-old SAT-solvers on new computer hardware with modern SAT-solvers on 20-year-old hardware. Our findings show that the progress on the algorithmic side has at least as much impact as the progress on the hardware side.

“A Bayesian Approach to the Simulation Argument”, Kipping 2020

“A Bayesian Approach to the Simulation Argument”⁠, David Kipping (2020-08-03; backlinks):

The Simulation Argument posed by Bostrom suggests that we may be living inside a sophisticated computer simulation. If posthuman civilizations eventually have both the capability and desire to generate such Bostrom-like simulations, then the number of simulated realities would greatly exceed the one base reality, ostensibly indicating a high probability that we do not live in said base reality.

In this work, it is argued that since the hypothesis that such simulations are technically possible remains unproven, statistical calculations need to consider not just the number of state spaces, but the intrinsic model uncertainty. This is achievable through a Bayesian treatment of the problem, which is presented here. Using Bayesian model averaging, it is shown that the probability that we are sims is in fact less than 50%, tending towards that value in the limit of an infinite number of simulations. This result is broadly indifferent as to whether one conditions upon the fact that humanity has not yet birthed such simulations, or ignore it.

As argued elsewhere, it is found that if humanity does start producing such simulations, then this would radically shift the odds and make it very probably we are in fact simulated.

[Keywords: simulation argument, Bayesian inference]

“Data Movement Is All You Need: A Case Study on Optimizing Transformers”, Ivanov et al 2020

“Data Movement Is All You Need: A Case Study on Optimizing Transformers”⁠, Andrei Ivanov, Nikoli Dryden, Tal Ben-Nun, Shigang Li, Torsten Hoefler (2020-06-30; ai):

Transformers are one of the most important machine learning workloads today. Training one is a very compute-intensive task, often taking days or weeks, and significant attention has been given to optimizing transformers. Despite this, existing implementations do not efficiently utilize GPUs. We find that data movement is the key bottleneck when training. Due to Amdahl’s Law and massive improvements in compute performance, training has now become memory-bound. Further, existing frameworks use suboptimal data layouts. Using these insights, we present a recipe for globally optimizing data movement in transformers. We reduce data movement by up to 22.91% and overall achieve a 1.30× performance improvement over state-of-the-art frameworks when training a BERT encoder layer and 1.19× for the entire BERT. Our approach is applicable more broadly to optimizing deep neural networks, and offers insight into how to tackle emerging performance bottlenecks.

“Sample Factory: Egocentric 3D Control from Pixels at 100,000 FPS With Asynchronous Reinforcement Learning”, Petrenko et al 2020

“Sample Factory: Egocentric 3D Control from Pixels at 100,000 FPS with Asynchronous Reinforcement Learning”⁠, Aleksei Petrenko, Zhehui Huang, Tushar Kumar, Gaurav Sukhatme, Vladlen Koltun (2020-06-21; backlinks):

Increasing the scale of reinforcement learning experiments has allowed researchers to achieve unprecedented results in both training sophisticated agents for video games, and in sim-to-real transfer for robotics. Typically such experiments rely on large distributed systems and require expensive hardware setups, limiting wider access to this exciting area of research. In this work we aim to solve this problem by optimizing the efficiency and resource utilization of reinforcement learning algorithms instead of relying on distributed computation. We present the “Sample Factory”, a high-throughput training system optimized for a single-machine setting. Our architecture combines a highly efficient, asynchronous, GPU-based sampler with off-policy correction techniques, allowing us to achieve throughput higher than 10⁵ environment frames/​​second on non-trivial control problems in 3D without sacrificing sample efficiency. We extend Sample Factory to support self-play and population-based training and apply these techniques to train highly capable agents for a multiplayer first-person shooter game. The source code is available at https:/​​/​​github.com/​​alex-petrenko/​​sample-factory

“There’s Plenty of Room at the Top: What Will Drive Computer Performance After Moore’s Law?”, Leiserson et al 2020

2020-leiserson.pdf: “There’s plenty of room at the Top: What will drive computer performance after Moore’s law?”⁠, Charles E. Leiserson, Neil C. Thompson, Joel S. Emer, Bradley C. Kuszmaul, Butler W. Lampson, Daniel Sanchez, et al (2020-06-05; ai; backlinks):

From bottom to top: The doubling of the number of transistors on a chip every 2 years, a seemly inevitable trend that has been called Moore’s law, has contributed immensely to improvements in computer performance. However, silicon-based transistors cannot get much smaller than they are today, and other approaches should be explored to keep performance growing. Leiserson et al review recent examples and argue that the most promising place to look is at the top of the computing stack, where improvements in software, algorithms, and hardware architecture can bring the much-needed boost…The miniaturization of semiconductor transistors has driven the growth in computer performance for more than 50 years. As miniaturization approaches its limits, bringing an end to Moore’s law, performance gains will need to come from software, algorithms, and hardware. We refer to these technologies as the “Top” of the computing stack to distinguish them from the traditional technologies at the “Bottom”: semiconductor physics and silicon-fabrication technology. In the post-Moore era, the Top will provide substantial performance gains, but these gains will be opportunistic, uneven, and sporadic, and they will suffer from the law of diminishing returns⁠. Big system components offer a promising context for tackling the challenges of working at the Top.

…Unfortunately, semiconductor miniaturization is running out of steam as a viable way to grow computer performance—there isn’t much more room at the “Bottom.” If growth in computing power stalls, practically all industries will face challenges to their productivity. Nevertheless, opportunities for growth in computing performance will still be available, especially at the “Top” of the computing-technology stack: software, algorithms, and hardware architecture.

Advances: Software can be made more efficient by performance engineering: restructuring software to make it run faster. Performance engineering can remove inefficiencies in programs, known as software bloat, arising from traditional software-development strategies that aim to minimize an application’s development time rather than the time it takes to run. Performance engineering can also tailor software to the hardware on which it runs, for example, to take advantage of parallel processors and vector units.

Algorithms offer more-efficient ways to solve problems. Indeed, since the late 1970s, the time to solve the maximum-flow problem improved nearly as much from algorithmic advances as from hardware speedups. But progress on a given algorithmic problem occurs unevenly and sporadically and must ultimately face diminishing returns. As such, we see the biggest benefits coming from algorithms for new problem domains (eg. machine learning) and from developing new theoretical machine models that better reflect emerging hardware.

Hardware architectures can be streamlined—for instance, through processor simplification, where a complex processing core is replaced with a simpler core that requires fewer transistors. The freed-up transistor budget can then be redeployed in other ways—for example, by increasing the number of processor cores running in parallel, which can lead to large efficiency gains for problems that can exploit parallelism. Another form of streamlining is domain specialization, where hardware is customized for a particular application domain. This type of specialization jettisons processor functionality that is not needed for the domain. It can also allow more customization to the specific characteristics of the domain, for instance, by decreasing floating-point precision for machine-learning applications.

In the post-Moore era, performance improvements from software, algorithms, and hardware architecture will increasingly require concurrent changes across other levels of the stack. These changes will be easier to implement, from engineering-management and economic points of view, if they occur within big system components: reusable software with typically more than a million lines of code or hardware of comparable complexity. When a single organization or company controls a big component, modularity can be more easily re-engineered to obtain performance gains. Moreover, costs and benefits can be pooled so that important but costly changes in one part of the big component can be justified by benefits elsewhere in the same component.

OUTLOOK: As miniaturization wanes, the silicon-fabrication improvements at the Bottom will no longer provide the predictable, broad-based gains in computer performance that society has enjoyed for more than 50 years. Software performance engineering, development of algorithms, and hardware streamlining at the Top can continue to make computer applications faster in the post-Moore era. Unlike the historical gains at the Bottom, however, gains at the Top will be opportunistic, uneven, and sporadic. Moreover, they will be subject to diminishing returns as specific computations become better explored.

“Measuring the Algorithmic Efficiency of Neural Networks”, Hernandez & Brown 2020

“Measuring the Algorithmic Efficiency of Neural Networks”⁠, Danny Hernandez, Tom B. Brown (2020-05-08; ai⁠, economics /​ ​experience-curve⁠, fiction /​ ​text-game⁠, prediction; backlinks):

Three factors drive the advance of AI: algorithmic innovation, data, and the amount of compute available for training. Algorithmic progress has traditionally been more difficult to quantify than compute and data. In this work, we argue that algorithmic progress has an aspect that is both straightforward to measure and interesting: reductions over time in the compute needed to reach past capabilities. We show that the number of floating-point operations required to train a classifier to AlexNet-level performance on ImageNet has decreased by a factor of 44× between 2012 and 2019. This corresponds to algorithmic efficiency doubling every 16 months over a period of 7 years. By contrast, Moore’s Law would only have yielded an 11× cost improvement. We observe that hardware and algorithmic efficiency gains multiply and can be on a similar scale over meaningful horizons, which suggests that a good model of AI progress should integrate measures from both.

“Psychic Paper”, Siguza 2020

“Psychic Paper”⁠, Siguza (2020-05-01; backlinks):

[Writeup of a major Apple iOS vulnerability: any application could access most of the system by simply sending the OS an XML document requesting access to permissions it was allowed, and then, inside an XML “comment”, including a request for all other permissions. Because iOS uses multiple libraries to parse XML documents, which all disagree on what is valid XML and how comments are handled, the outer request was valid for the first check (that it was not requesting permissions it should not) but then the inner request hidden in the comment would be parsed and since it was supposedly already checked and proven safe, the additional request would go through, granting all permissions. Oops.]

“Magic: the Gathering Is As Hard As Arithmetic”, Biderman 2020

“Magic: the Gathering is as Hard as Arithmetic”⁠, Stella Biderman (2020-03-11; backlinks):

Magic: the Gathering is a popular and famously complicated card game about magical combat. Recently, several authors including Chatterjee and Ibsen-Jensen (2016) and Churchill et al 2019 have investigated the computational complexity of playing Magic optimally.

In this paper we show that the “mate-in-n” problem for Magic is Δ[^0^~*n*~]{.supsub}-hard and that optimal play in two-player Magic is non-arithmetic in general. These results apply to how real Magic is played, can be achieved using standard-size tournament legal decks, and do not rely on stochasticity or hidden information.

Our paper builds upon the construction that Churchill, Biderman, and Herrick (2019) used to show that this problem was at least as hard as the halting problem.

“Recalibrating Global Data Center Energy-use Estimates”, Masanet et al 2020

2020-masanet.pdf: “Recalibrating global data center energy-use estimates”⁠, Eric Masanet, Arman Shehabi, Nuoa Lei, Sarah Smith, Jonathan Koomey (2020-02-28)

“Recursed Is Not Recursive: A Jarring Result”, Demaine et al 2020

“Recursed is not Recursive: A Jarring Result”⁠, Erik Demaine, Justin Kopinsky, Jayson Lynch (2020-02-12; backlinks):

Recursed is a 2D puzzle platform video game featuring treasure chests that, when jumped into, instantiate a room that can later be exited (similar to function calls), optionally generating a jar that returns back to that room (similar to continuations). We prove that Recursed is RE-complete and thus undecidable (not recursive) by a reduction from the Post Correspondence Problem. Our reduction is “practical”: the reduction from PCP results in fully playable levels that abide by all constraints governing levels (including the 15×20 room size) designed for the main game. Our reduction is also “efficient”: a Turing machine can be simulated by a Recursed level whose size is linear in the encoding size of the Turing machine and whose solution length is polynomial in the running time of the Turing machine.

“The 1-Bit Instrument: The Fundamentals of 1-Bit Synthesis, Their Implementational Implications, and Instrumental Possibilities”, Troise 2020

2020-troise.pdf: “The 1-Bit Instrument: The Fundamentals of 1-Bit Synthesis, Their Implementational Implications, and Instrumental Possibilities”⁠, Blake Troise (2020-01-01):

The 1-bit sonic environment (perhaps most famously musically employed on the ZX Spectrum) is defined by extreme limitation. Yet, belying these restrictions, there is a surprisingly expressive instrumental versatility. This article explores the theory behind the primary, idiosyncratically 1-bit techniques available to the composer-programmer, those that are essential when designing “instruments” in 1-bit environments. These techniques include pulse width modulation for timbral manipulation and means of generating virtual polyphony in software, such as the pin pulse and pulse interleaving techniques. These methodologies are considered in respect to their compositional implications and instrumental applications.

[Keywords: chiptune, 1-bit, one-bit, ZX Spectrum, pulse pin method, pulse interleaving, timbre, polyphony, history]

“Hyrum's Law: An Observation on Software Engineering”, Wright 2019

“Hyrum's Law: An observation on Software Engineering”⁠, Hyrum Wright (2019-11; technology; backlinks):

With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.

…Taken to its logical extreme, this leads to the following observation, colloquially referred to as “The Law of Implicit Interfaces”: Given enough use, there is no such thing as a ‘private’ implementation⁠. That is, if an interface has enough consumers, they will collectively depend on every aspect of the implementation, intentionally or not. This effect serves to constrain changes to the implementation, which must now conform to both the explicitly documented interface, as well as the implicit interface captured by usage. We often refer to this phenomenon as “bug-for-bug compatibility.”

The creation of the implicit interface usually happens gradually, and interface consumers generally aren’t aware as it’s happening. For example, an interface may make no guarantees about performance, yet consumers often come to expect a certain level of performance from its implementation. Those expectations become part of the implicit interface to a system, and changes to the system must maintain these performance characteristics to continue functioning for its consumers.

…I’m a Software Engineer at Google, working on large-scale code change tooling and infrastructure. Prior to that, I spent 5 years improving Google’s core C++ libraries. The above observation grew out of experiences when even the simplest library change caused failures in some far off system.

[XKCD]

[Software Engineering at Google: Lessons Learned from Programming Over Time⁠, Winters et al 2020:

Some languages specifically randomize hash ordering between library versions or even between execution of the same program in an attempt to prevent dependencies. But even this still allows for some Hyrum’s Law surprises: there is code that uses hash iteration ordering as an inefficient random-number generator. Removing such randomness now would break those users. Just as entropy increases in every thermodynamic system, Hyrum’s Law applies to every observable behavior.

SRE book, ch4 “Service Level Objectives”:

An SLO is a service level objective: a target value or range of values for a service level that is measured by an SLI. A natural structure for SLOs is thus SLI ≤ target, or lower bound ≤ SLI ≤ upper bound. For example, we might decide that we will return Shakespeare search results “quickly”, adopting an SLO that our average search request latency should be less than 100 milliseconds…Choosing and publishing SLOs to users sets expectations about how a service will perform. This strategy can reduce unfounded complaints to service owners about, for example, the service being slow. Without an explicit SLO, users often develop their own beliefs about desired performance, which may be unrelated to the beliefs held by the people designing and operating the service. This dynamic can lead to both over-reliance on the service, when users incorrectly believe that a service will be more available than it actually is (as happened with Chubby: see “The Global Chubby Planned Outage”), and under-reliance, when prospective users believe a system is flakier and less reliable than it actually is.

“The Global Chubby Planned Outage”

[Written by Marc Alvidrez]

Chubby [Bur06] is Google’s lock service for loosely coupled distributed systems. In the global case, we distribute Chubby instances such that each replica is in a different geographic region. Over time, we found that the failures of the global instance of Chubby consistently generated service outages, many of which were visible to end users. As it turns out, true global Chubby outages are so infrequent that service owners began to add dependencies to Chubby assuming that it would never go down. Its high reliability provided a false sense of security because the services could not function appropriately when Chubby was unavailable, however rarely that occurred.

The solution to this Chubby scenario is interesting: SRE makes sure that global Chubby meets, but does not substantially exceed, its service level objective. In any given quarter, if a true failure has not dropped availability below the target, a controlled outage will be synthesized by intentionally taking down the system. In this way, we are able to flush out unreasonable dependencies on Chubby shortly after they are added. Doing so forces service owners to reckon with the reality of distributed systems sooner rather than later.

…Don’t overachieve:

Users build on the reality of what you offer, rather than what you say you’ll supply, particularly for infrastructure services. If your service’s actual performance is much better than its stated SLO, users will come to rely on its current performance. You can avoid over-dependence by deliberately taking the system offline occasionally (Google’s Chubby service introduced planned outages in response to being overly available),18 throttling some requests, or designing the system so that it isn’t faster under light loads.]

See Also:

• “The History of the URL”

• “Why Johnny Won’t Upgrade”

“Local-First Software: You Own Your Data, in spite of the Cloud [paper]”, Kleppmann et al 2019

2019-kleppmann.pdf: “Local-First Software: You Own Your Data, in spite of the Cloud [paper]”⁠, Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, Mark McGranaghan (2019-10-23; backlinks):

Cloud apps like Google Docs and Trello are popular because they enable real-time collaboration with colleagues, and they make it easy for us to access our work from all of our devices. However, by centralizing data storage on servers, cloud apps also take away ownership and agency from users. If a service shuts down, the software stops functioning, and data created with that software is lost.

In this article we propose local-first software, a set of principles for software that enables both collaboration and ownership for users. Local-first ideals include the ability to work offline and collaborate across multiple devices, while also improving the security, privacy, long-term preservation, and user control of data.

We survey existing approaches to data storage and sharing, ranging from email attachments to web apps to Firebase-backed mobile apps, and we examine the trade-offs of each. We look at Conflict-free Replicated Data Types (CRDTs): data structures that are multi-user from the ground up while also being fundamentally local and private. CRDTs have the potential to be a foundational technology for realizing local-first software.

We share some of our findings from developing local-first software prototypes at the Ink & Switch research lab over the course of several years. These experiments test the viability of CRDTs in practice, and explore the user interface challenges for this new data model. Lastly, we suggest some next steps for moving towards local-first software: for researchers, for app developers, and a startup opportunity for entrepreneurs.

[Keywords: collaboration software, mobile computing, data ownership, CRDTs, peer-to-peer communication]

“Mixed-Signal Neuromorphic Processors: Quo Vadis?”, Bavandpour et al 2019

2019-bavandpour.pdf: “Mixed-Signal Neuromorphic Processors: Quo vadis?”⁠, Mohammad Bavandpour, Mohammad Reza Mahmoodi, Shubham Sahay, Dmitri B. Strukov (2019-10-14):

This paper outlines different design options and most suitable memory devices for implementing dense vector-by-matrix multiplication operation, the key operation in neuromorphic computing⁠.

The considered approaches are evaluated by modeling system-level performance of 55-nm 4-bit mixed-signal neuromorphic inference processor running common deep learning feedforward and recurrent neural network models.

[Keywords: nonvolatile memory device, mixed-signal circuits, neuromorphic processor, vector-by-matrix multiplication]

“The Busy Beaver Frontier”, Aaronson 2019

2019-aaronson.pdf: “The Busy Beaver Frontier”⁠, Scott Aaronson (2019-08-28):

The Busy Beaver function⁠, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction⁠, emphasizing lesser-known insights, recent progress, and especially favorite open problems.

Examples of such problems include: when does the BB function first exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n + 1) > 2^BB(n) for large enough n? Given BB(n), how many advice bits are needed to compute BB(n + 1)? Do all Busy Beavers halt on all inputs, not just the 0 input? Is it decidable, given n, whether BB(n) is even or odd? [See also “Collatz-like behavior of Busy Beavers” & FRACTRAN & “Maybe the Spaghetti Code Conjecture is False”⁠/​​“A Busy Beaver Champion Program Derived from Scratch”⁠.]

“Moral Permissibility of Action Plans”, Lindner et al 2019

“Moral Permissibility of Action Plans”⁠, Felix Lindner, Robert Mattmüller, Bernhard Nebel (2019-07-17; philosophy /​ ​ethics):

Research in classical planning so far was mainly concerned with generating a satisficing or an optimal plan. However, if such systems are used to make decisions that are relevant to humans, one should also consider the ethical consequences generated plans can have. We address this challenge by analyzing in how far it is possible to generalize existing approaches of machine ethics to automatic planning systems⁠. Traditionally, ethical principles are formulated in an action-based manner, allowing to judge the execution of one action. We show how such a judgment can be generalized to plans. Further, we study the computational complexity of making ethical judgment about plans.

…We exemplified and explained our formalizations using classical moral dilemmas such as the trolley problem⁠, and identified how and for which reasons different principles may arrive at different (or the same) conclusions. Furthermore, we studied the computational complexity of verifying whether a given plan is permissible with respect to each of the 5 investigated principles. We saw that, with respect to our formalization, verification is PSPACE-complete for utilitarianism⁠, co-NP-complete for do-no-harm⁠, for do-no-instrumental-harm, and for the doctrine of double effect⁠, and that it is polynomial-time for deontology⁠. It turned out that verifying the do-no-harm principles involves a combinatorial reasoning over possible sets of actions that lead to harm or that may be instrumental towards achieving a goal condition, which makes verifying those ethical principles surprisingly hard

“ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data”, Stehle & Jacobsen 2019

“ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data”⁠, Elias Stehle, Hans-Arno Jacobsen (2019-05-31; backlinks):

Parsing is essential for a wide range of use cases, such as stream processing, bulk loading, and in-situ querying of raw data. Yet, the compute-intense step often constitutes a major bottleneck in the data ingestion pipeline, since parsing of inputs that require more involved parsing rules is challenging to parallelize. This work proposes a massively parallel algorithm for parsing delimiter-separated data formats on GPUs. Other than the state-of-the-art, the proposed approach does not require an initial sequential pass over the input to determine a thread’s parsing context. That is, how a thread, beginning somewhere in the middle of the input, should interpret a certain symbol (eg. whether to interpret a comma as a delimiter or as part of a larger string enclosed in double-quotes). Instead of tailoring the approach to a single format, we are able to perform a massively parallel FSM simulation, which is more flexible and powerful, supporting more expressive parsing rules with general applicability. Achieving a parsing rate of as much as 14.2 GB/​​s, our experimental evaluation on a GPU with 3584 cores shows that the presented approach is able to scale to thousands of cores and beyond. With an end-to-end streaming approach, we are able to exploit the full-duplex capabilities of the PCIe bus and hide latency from data transfers. Considering the end-to-end performance, the algorithm parses 4.8 GB in as little as 0.44 seconds, including data transfers.

“Local-first Software: You Own Your Data, in spite of the Cloud [web]”, Kleppmann et al 2019

“Local-first software: You own your data, in spite of the cloud [web]”⁠, Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, Mark McGranaghan (Ink & Switch) (2019-04; design; backlinks):

[PDF version]

Cloud apps like Google Docs and Trello are popular because they enable real-time collaboration with colleagues, and they make it easy for us to access our work from all of our devices. However, by centralizing data storage on servers, cloud apps also take away ownership and agency from users. If a service shuts down, the software stops functioning, and data created with that software is lost.

In this article we propose “local-first software”: a set of principles for software that enables both collaboration and ownership for users. Local-first ideals include the ability to work offline and collaborate across multiple devices, while also improving the security, privacy, long-term preservation, and user control of data.

We survey existing approaches to data storage and sharing, ranging from email attachments to web apps to Firebase-backed mobile apps, and we examine the trade-offs of each. We look at Conflict-free Replicated Data Types (CRDTs): data structures that are multi-user from the ground up while also being fundamentally local and private. CRDTs have the potential to be a foundational technology for realizing local-first software.

We share some of our findings from developing local-first software prototypes at Ink & Switch over the course of several years. These experiments test the viability of CRDTs in practice, and explore the user interface challenges for this new data model. Lastly, we suggest some next steps for moving towards local-first software: for researchers, for app developers, and a startup opportunity for entrepreneurs.

…in the cloud, ownership of data is vested in the servers, not the users, and so we became borrowers of our own data. The documents created in cloud apps are destined to disappear when the creators of those services cease to maintain them. Cloud services defy long-term preservation. No Wayback Machine can restore a sunsetted web application. The Internet Archive cannot preserve your Google Docs.

In this article we explored a new way forward for software of the future. We have shown that it is possible for users to retain ownership and control of their data, while also benefiting from the features we associate with the cloud: seamless collaboration and access from anywhere. It is possible to get the best of both worlds.

But more work is needed to realize the local-first approach in practice. Application developers can take incremental steps, such as improving offline support and making better use of on-device storage. Researchers can continue improving the algorithms, programming models, and user interfaces for local-first software. Entrepreneurs can develop foundational technologies such as CRDTs and peer-to-peer networking into mature products able to power the next generation of applications.

• Motivation: collaboration and ownership

• Seven ideals for local-first software

  • No spinners: your work at your fingertips
  • Your work is not trapped on one device
  • The network is optional
  • Seamless collaboration with your colleagues
  • The Long Now
  • Security and privacy by default
  • You retain ultimate ownership and control

• Existing data storage and sharing models

  • How application architecture affects user experience
    • Files and email attachments
    • Web apps: Google Docs, Trello, Figma
    • Dropbox, Google Drive, Box, OneDrive, etc.
    • Git and GitHub
  • Developer infrastructure for building apps
    • Web app (thin client)
    • Mobile app with local storage (thick client)
    • Backend-as-a-Service: Firebase, CloudKit, Realm
    • CouchDB

• Towards a better future

  • CRDTs as a foundational technology
  • Ink & Switch prototypes
    • Trello clone
    • Collaborative drawing
    • Media canvas
    • Findings
  • How you can help
    • For distributed systems and programming languages researchers
    • For Human-Computer Interaction (HCI) researchers
    • For practitioners
    • Call for startups

• Conclusions

“Magic: The Gathering Is Turing Complete”, Churchill et al 2019

“Magic: The Gathering is Turing Complete”⁠, Alex Churchill, Stella Biderman, Austin Herrick (2019-03-24; backlinks):

Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been open for a decade.

To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable.

We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.

“Parsing Gigabytes of JSON per Second”, Langdale & Lemire 2019

“Parsing Gigabytes of JSON per Second”⁠, Geoff Langdale, Daniel Lemire (2019-02-22; backlinks):

JavaScript Object Notation or JSON is a ubiquitous data exchange format on the Web. Ingesting JSON documents can become a performance bottleneck due to the sheer volume of data. We are thus motivated to make JSON parsing as fast as possible.

Despite the maturity of the problem of JSON parsing, we show that substantial speedups are possible. We present the first standard-compliant JSON parser to process gigabytes of data per second on a single core, using commodity processors. We can use a quarter or fewer instructions than a state-of-the-art reference parser like RapidJSON. Unlike other validating parsers, our software (simdjson) makes extensive use of Single Instruction, Multiple Data (SIMD) instructions. To ensure reproducibility, simdjson is freely available as open-source software under a liberal license.

“Spectre Is Here to Stay: An Analysis of Side-channels and Speculative Execution”, Mcilroy et al 2019

“Spectre is here to stay: An analysis of side-channels and speculative execution”⁠, Ross Mcilroy, Jaroslav Sevcik, Tobias Tebbi, Ben L. Titzer, Toon Verwaest (2019-02-14; backlinks):

The recent discovery of the Spectre and Meltdown attacks represents a watershed moment not just for the field of Computer Security, but also of Programming Languages. This paper explores speculative side-channel attacks and their implications for programming languages. These attacks leak information through micro-architectural side-channels which we show are not mere bugs, but in fact lie at the foundation of optimization. We identify three open problems, (1) finding side-channels, (2) understanding speculative vulnerabilities, and (3) mitigating them. For (1) we introduce a mathematical meta-model that clarifies the source of side-channels in simulations and CPUs. For (2) we introduce an architectural model with speculative semantics to study recently-discovered vulnerabilities. For (3) we explore and evaluate software mitigations and prove one correct for this model. Our analysis is informed by extensive offensive research and defensive implementation work for V8, the production JavaScript virtual machine in Chrome. Straightforward extensions to model real hardware suggest these vulnerabilities present formidable challenges for effective, efficient mitigation. As a result of our work, we now believe that speculative vulnerabilities on today’s hardware defeat all language-enforced confidentiality with no known comprehensive software mitigations, as we have discovered that untrusted code can construct a universal read gadget to read all memory in the same address space through side-channels. In the face of this reality, we have shifted the security model of the Chrome web browser and V8 to process isolation.

“Dataset Distillation”, Wang et al 2018

“Dataset Distillation”⁠, Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, Alexei A. Efros (2018-11-27; backlinks):

Model distillation aims to distill the knowledge of a complex model into a simpler one. In this paper, we consider an alternative formulation called dataset distillation: we keep the model fixed and instead attempt to distill the knowledge from a large training dataset into a small one. The idea is to synthesize a small number of data points that do not need to come from the correct data distribution, but will, when given to the learning algorithm as training data, approximate the model trained on the original data. For example, we show that it is possible to compress 60,000 MNIST training images into just 10 synthetic distilled images (one per class) and achieve close to original performance with only a few gradient descent steps, given a fixed network initialization. We evaluate our method in various initialization settings and with different learning objectives. Experiments on multiple datasets show the advantage of our approach compared to alternative methods.

“Adversarial Reprogramming of Text Classification Neural Networks”, Neekhara et al 2018

“Adversarial Reprogramming of Text Classification Neural Networks”⁠, Paarth Neekhara, Shehzeen Hussain, Shlomo Dubnov, Farinaz Koushanfar (2018-09-06; ai /​ ​adversarial⁠,  /​ ​gpt⁠, fiction; backlinks):

Adversarial Reprogramming has demonstrated success in utilizing pre-trained neural network classifiers for alternative classification tasks without modification to the original network. An adversary in such an attack scenario trains an additive contribution to the inputs to repurpose the neural network for the new classification task. While this reprogramming approach works for neural networks with a continuous input space such as that of images, it is not directly applicable to neural networks trained for tasks such as text classification, where the input space is discrete. Repurposing such classification networks would require the attacker to learn an adversarial program that maps inputs from one discrete space to the other. In this work, we introduce a context-based vocabulary remapping model to reprogram neural networks trained on a specific sequence classification task, for a new sequence classification task desired by the adversary. We propose training procedures for this adversarial program in both white-box and black-box settings. We demonstrate the application of our model by adversarially repurposing various text-classification models including LSTM, bi-directional LSTM and CNN for alternate classification tasks.

“Breaking POps/J Barrier With Analog Multiplier Circuits Based on Nonvolatile Memories”, Mahmoodi & Strukov 2018

2018-mahmoodi.pdf: “Breaking POps/J Barrier with Analog Multiplier Circuits Based on Nonvolatile Memories”⁠, M. Reza Mahmoodi, Dmitri Strukov (2018-07-23):

Low-to-medium resolution analog vector-by-matrix multipliers (VMMs) offer a remarkable energy/​​area efficiency as compared to their digital counterparts. Still, the maximum attainable performance in analog VMMs is often bounded by the overhead of the peripheral circuits.

The main contribution of this paper is the design of novel sensing circuitry which improves energy-efficiency and density of analog multipliers. The proposed circuit is based on translinear Gilbert cell, which is topologically combined with a floating nonlinear resistor and a low-gain amplifier. Several compensation techniques are employed to ensure reliability with respect to process, temperature, and supply voltage variations.

As a case study, we consider implementation of couple-gate current-mode VMM with embedded split-gate NOR flash memory. Our simulation results show that a 4-bit 100×100 VMM circuit designed in 55 nm CMOS technology achieves the record-breaking performance of 3.63 POps/​​J.

[Keywords: analog computing, sensing circuit, floating-gate memory, current processing, vector-matrix multiplier, artificial neural networks]

“Adversarial Reprogramming of Neural Networks”, Elsayed et al 2018

“Adversarial Reprogramming of Neural Networks”⁠, Gamaleldin F. Elsayed, Ian Goodfellow, Jascha Sohl-Dickstein (2018-06-28; ai /​ ​adversarial⁠,  /​ ​gpt⁠, fiction; backlinks):

Deep neural networks are susceptible to adversarial attacks. In computer vision, well-crafted perturbations to images can cause neural networks to make mistakes such as confusing a cat with a computer. Previous adversarial attacks have been designed to degrade performance of models or cause machine learning models to produce specific outputs chosen ahead of time by the attacker. We introduce attacks that instead reprogram the target model to perform a task chosen by the attacker—without the attacker needing to specify or compute the desired output for each test-time input. This attack finds a single adversarial perturbation, that can be added to all test-time inputs to a machine learning model in order to cause the model to perform a task chosen by the adversary—even if the model was not trained to do this task. These perturbations can thus be considered a program for the new task. We demonstrate adversarial reprogramming on six ImageNet classification models, repurposing these models to perform a counting task, as well as classification tasks: classification of MNIST and CIFAR-10 examples presented as inputs to the ImageNet model.

“Security, Moore’s Law, and the Anomaly of Cheap Complexity”, Flake 2018

“Security, Moore’s law, and the anomaly of cheap complexity”⁠, Halvar Flake (2018-05-29; backlinks):

CyCon Tallinn 2019, Keynote: Security, Moore’s law, and the anomaly of cheap complexity

I was invited to Keynote CyCon, and my talk was supposed to be right before Bruce Schneier’s talk. I tried hard to make a talk that is accessible to people with a non-technical and non-engineering background, which nonetheless summarized the important things I had learnt about security. The core points are:

1. CPUs are much more complex than 20 years ago, the feeling of being overwhelmed by complexity is not an illusion.
2. We are sprinkling chips into objects like we are putting salt on food.
3. We do this because complexity is cheaper than simplicity. We often use a cheap but complex computer to simulate a much simpler device for cost and convenience.
4. The inherent complexity/​​power of the underlying computer has a tendency to break to the surface as soon as something goes wrong.
5. Discrete Dynamical Systems and computers share many properties, and tiny changes have a tendency to cause large changes quickly.

This may be the most polished talk I have ever given—I did multiple dry-runs with different audiences, and bothered everybody and his dog with the slides.

I am particularly proud that Bruce Schneier seemed to have liked it⁠; this is a big thing for me because reading “Applied Cryptography” and “A self-study course in block-cipher cryptanalysis” had a pretty substantial impact on my life.

“Weird Machines, Exploitability, and Provable Unexploitability”, Dullien 2017

“Weird machines, exploitability, and provable unexploitability”⁠, Thomas Dullien (2017-12-19; backlinks):

The concept of exploit is central to computer security, particularly in the context of memory corruptions. Yet, in spite of the centrality of the concept and voluminous descriptions of various exploitation techniques or countermeasures, a good theoretical framework for describing and reasoning about exploitation has not yet been put forward.

A body of concepts and folk theorems exists in the community of exploitation practitioners; unfortunately, these concepts are rarely written down or made sufficiently precise for people outside of this community to benefit from them. This paper clarifies a number of these concepts, provides a clear definition of exploit, a clear definition of the concept of a weird machine, and how programming of a weird machine leads to exploitation. The papers also shows, somewhat counterintuitively, that it is feasible to design some software in a way that even powerful attackers—with the ability to corrupt memory once—cannot gain an advantage.

The approach in this paper is focused on memory corruptions. While it can be applied to many security vulnerabilities introduced by other programming mistakes, it does not address side channel attacks, protocol weaknesses, or security problems that are present by design.

[Keywords: Computer Security, Computer hacking, Computation Theory, Information security, Language-theoretic security]

“Analogue Signal and Image Processing With Large Memristor Crossbars”, Li et al 2017

2017-li.pdf: “Analogue signal and image processing with large memristor crossbars”⁠, Can Li, Miao Hu, Yunning Li, Hao Jiang, Ning Ge, Eric Montgomery, Jiaming Zhang, Wenhao Song, Noraica Davila, et al (2017-12-04):

Memristor crossbars offer reconfigurable non-volatile resistance states and could remove the speed and energy efficiency bottleneck in vector-matrix multiplication, a core computing task in signal and image processing. Using such systems to multiply an analogue-voltage-amplitude-vector by an analogue-conductance-matrix at a reasonably large scale has, however, proved challenging due to difficulties in device engineering and array integration.

Here we show that reconfigurable memristor crossbars composed of hafnium oxide memristors on top of metal-oxide-semiconductor transistors are capable of analogue vector-matrix multiplication with array sizes of up to 128 × 64 cells.

Our output precision (5–8 bits, depending on the array size) is the result of high device yield (99.8%) and the multilevel, stable states of the memristors, while the linear device current-voltage characteristics and low wire resistance between cells leads to high accuracy.

With the large memristor crossbars, we demonstrate signal processing, image compression and convolutional filtering, which are expected to be important applications in the development of the Internet of Things (IoT) and edge computing.

“Computer Latency: 1977–2017”, Luu 2017

“Computer latency: 1977–2017”⁠, Dan Luu (2017-12; dual-n-back; backlinks):

I’ve had this nagging feeling that the computers I use today feel slower than the computers I used as a kid. As a rule, I don’t trust this kind of feeling because human perception has been shown to be unreliable in empirical studies, so I carried around a high-speed camera and measured the response latency of devices I’ve run into in the past few months. These are tests of the latency between a keypress and the display of a character in a terminal (see appendix for more details)…If we look at overall results, the fastest machines are ancient. Newer machines are all over the place. Fancy gaming rigs with unusually high refresh-rate displays are almost competitive with machines from the late 70s and early 80s, but “normal” modern computers can’t compete with thirty to forty year old machines.

…Almost every computer and mobile device that people buy today is slower than common models of computers from the 70s and 80s. Low-latency gaming desktops and the iPad Pro can get into the same range as quick machines from thirty to forty years ago, but most off-the-shelf devices aren’t even close.

If we had to pick one root cause of latency bloat, we might say that it’s because of “complexity”. Of course, we all know that complexity is bad. If you’ve been to a non-academic non-enterprise tech conference in the past decade, there’s a good chance that there was at least one talk on how complexity is the root of all evil and we should aspire to reduce complexity.

Unfortunately, it’s a lot harder to remove complexity than to give a talk saying that we should remove complexity. A lot of the complexity buys us something, either directly or indirectly. When we looked at the input of a fancy modern keyboard vs. the Apple 2 keyboard, we saw that using a relatively powerful and expensive general purpose processor to handle keyboard inputs can be slower than dedicated logic for the keyboard, which would both be simpler and cheaper. However, using the processor gives people the ability to easily customize the keyboard, and also pushes the problem of “programming” the keyboard from hardware into software, which reduces the cost of making the keyboard. The more expensive chip increases the manufacturing cost, but considering how much of the cost of these small-batch artisanal keyboards is the design cost, it seems like a net win to trade manufacturing cost for ease of programming.

“Keyboard Latency”, Luu 2017

“Keyboard latency”⁠, Dan Luu (2017-10-16; design⁠, technology; backlinks):

[Dan Luu continues his investigation of why computers feel so laggy and have such high latency compared to old computers (total computer latency⁠, terminal latency⁠, web bloat⁠, cf Pavel Fatin’s “Typing with pleasure” text editor analysis).

He measures 21 keyboard latencies using a logic analyzer, finding a range of 15–60ms (!), representing a waste of a large fraction of the available ~100–200ms latency budget before a user notices and is irritated (“the median keyboard today adds as much latency as the entire end-to-end pipeline as a fast machine from the 70s.”). The latency estimates are surprising, and do not correlate with advertised traits. They simply have to be measured empirically.]

We can see that, even with the limited set of keyboards tested, there can be as much as a 45ms difference in latency between keyboards. Moreover, a modern computer with one of the slower keyboards attached can’t possibly be as responsive as a quick machine from the 70s or 80s because the keyboard alone is slower than the entire response pipeline of some older computers. That establishes the fact that modern keyboards contribute to the latency bloat we’ve seen over the past forty years…Most keyboards add enough latency to make the user experience noticeably worse, and keyboards that advertise speed aren’t necessarily faster. The two gaming keyboards we measured weren’t faster than non-gaming keyboards, and the fastest keyboard measured was a minimalist keyboard from Apple that’s marketed more on design than speed.

“From Punched Cards to Flat Screens: A Technical Autobiography”, Hazel 2017

2017-hazel.pdf: “From Punched Cards to Flat Screens: A Technical Autobiography”⁠, Philip Hazel (2017-08-11)

“Terminal Latency”, Luu 2017

“Terminal Latency”⁠, Dan Luu (2017-07-18; dual-n-back; backlinks):

These graphs show the distribution of latencies for each terminal. The y-axis has the latency in milliseconds. The x-axis is the percentile (eg. 50 means represents 50%-ile keypress ie., the median keypress). Measurements are with macOS unless otherwise stated. The graph on the left is when the machine is idle, and the graph on the right is under load. If we just look at median latencies, some setups don’t look too bad—terminal.app and emacs-eshell are at roughly 5ms unloaded, small enough that many people wouldn’t notice. But most terminals (st, alacritty, hyper, and iterm2) are in the range where you might expect people to notice the additional latency even when the machine is idle. If we look at the tail when the machine is idle, say the 99.9%-ile latency, every terminal gets into the range where the additional latency ought to be perceptible, according to studies on user interaction. For reference, the internally generated keypress to GPU memory trip for some terminals is slower than the time it takes to send a packet from Boston to Seattle and back, about 70ms.

…Most terminals have enough latency that the user experience could be improved if the terminals concentrated more on latency and less on other features or other aspects of performance. However, when I search for terminal benchmarks, I find that terminal authors, if they benchmark anything, benchmark the speed of sinking stdout or memory usage at startup. This is unfortunate because most “low performance” terminals can already sink stdout many orders of magnitude faster than humans can keep up with, so further optimizing stdout throughput has a relatively small impact on actual user experience for most users. Likewise for reducing memory usage when an idle terminal uses 0.01% of the memory on my old and now quite low-end laptop. If you work on a terminal, perhaps consider relatively more latency and interactivity (eg. responsiveness to ^C) optimization and relatively less throughput and idle memory usage optimization.

“DAG Reduction: Fast Answering Reachability Queries”, Zhou et al 2017

2017-zhou.pdf: “DAG Reduction: Fast Answering Reachability Queries”⁠, Junfeng Zhou, Shijie Zhou, Jeffrey Xu Yu, Hao Wei, Ziyang Chen, Xian Tang (2017-05-01):

Answering reachability queries is one of the fundamental graph operations. The existing approaches build indexes and answer reachability queries on a directed acyclic graph (DAG) G, which is constructed by coalescing each strongly connected component of the given directed graph G into a node of G. Considering that G can still be large to be processed efficiently, there are studies to further reduce G to a smaller graph. However, these approaches suffer from either inefficiency in answering reachability queries, or cannot scale to large graphs.

In this paper, we study DAG reduction to accelerate reachability query processing, which reduces the size of G by computing transitive reduction (TR) followed by computing equivalence reduction (ER). For ER, we propose a divide-and-conquer algorithm, namely linear-ER. Given the result G^t of TR, linear-ER gets a smaller DAG G^ε in linear time based on equivalence relationship between nodes in G. Our DAG reduction approaches (TR and ER) substantially improve the cost of time and space, and can be scaled to large graphs. We confirm the efficiency of our approaches by extensive experimental studies for TR, ER, and reachability query processing using 20 real datasets.

“Web Bloat”, Luu 2017

“Web Bloat”⁠, Dan Luu (2017-02-08; dual-n-back; backlinks):

A couple years ago, I took a road trip from Wisconsin to Washington and mostly stayed in rural hotels on the way. I expected the internet in rural areas too sparse to have cable internet to be slow, but I was still surprised that a large fraction of the web was inaccessible. Some blogs with lightweight styling were readable, as were pages by academics who hadn’t updated the styling on their website since 1995. But very few commercial websites were usable (other than Google). When I measured my connection, I found that the bandwidth was roughly comparable to what I got with a 56k modem in the 90s. The latency and packet loss were substantially worse than the average day on dialup: latency varied between 500ms and 1000ms and packet loss varied between 1% and 10%. Those numbers are comparable to what I’d see on dialup on a bad day.

Despite my connection being only a bit worse than it was in the 90s, the vast majority of the web wouldn’t load…When Microsoft looked at actual measured connection speeds, they found that half of Americans don’t have broadband speed. Heck, AOL had 2 million dial-up subscribers in 2015, just AOL alone. Outside of the U.S., there are even more people with slow connections. I recently chatted with Ben Kuhn, who spends a fair amount of time in Africa, about his internet connection:

I’ve seen ping latencies as bad as ~45 sec and packet loss as bad as 50% on a mobile hotspot in the evenings from Jijiga, Ethiopia. (I’m here now and currently I have 150ms ping with no packet loss but it’s 10am). There are some periods of the day where it ~never gets better than 10 sec and ~10% loss. The internet has gotten a lot better in the past ~year; it used to be that bad all the time except in the early mornings.

…Let’s load some websites that programmers might frequent with a variety of simulated connections to get data on page load times…The timeout for tests was 6 minutes; anything slower than that is listed as FAIL. Pages that failed to load are also listed as FAIL. A few things that jump out from the table are:

1. A large fraction of the web is unusable on a bad connection. Even on a good (0% packet loss, no ping spike) dialup connection, some sites won’t load…If you were to look at the 90%-ile results, you’d see that most pages fail to load on dialup and the “Bad” and “😱” connections are hopeless for almost all sites.
2. Some sites will use a lot of data!

…The flaw in the “page weight doesn’t matter because average speed is fast” [claim] is that if you average the connection of someone in my apartment building (which is wired for 1Gbps internet) and someone on 56k dialup, you get an average speed of 500 Mbps. That doesn’t mean the person on dialup is actually going to be able to load a 5MB website. The average speed of 3.9 Mbps comes from a 2014 Akamai report, but it’s just an average. If you look at Akamai’s 2016 report, you can find entire countries where more than 90% of IP addresses are slower than that!..“Use bcrypt” has become the mantra for a reasonable default if you’re not sure what to do when storing passwords. The web would be a nicer place if “use webpagetest” caught on in the same way. It’s not always the best tool for the job, but it sure beats the current defaults.

“Mechanical Turing Machine in Wood Explained”, Ridel 2017

2017-ridel.pdf: “Mechanical Turing Machine in Wood Explained”⁠, Richard J. Ridel (2017-02-02)

“Architecting Energy-efficient STT-RAM Based Register File on GPGPUs via Delta Compression”, Zhang et al 2016

2016-zhang.pdf: “Architecting energy-efficient STT-RAM based register file on GPGPUs via delta compression”⁠, Hang Zhang, Xuhao Chen, Nong Xiao, Fang Liu (2016-06-05):

To facilitate efficient context switches, GPUs usually employ a large-capacity register file to accommodate a massive amount of context information. However, the large register file introduces high power consumption, flowing to high leakage power SRAM cells. Emerging non-volatile STT-RAM memory has recently been studied as a potential replacement to alleviate the leakage challenge when constructing register files on GPUs. Unfortunately, due to the long write latency and high energy consumption associated with write operations in STT-RAM, simply replacing SRAM with STT-RAM for register files would incur non-trivial performance overhead and only bring marginal energy benefits.

In this paper, we propose to optimize STT-RAM based GPU register files for better energy-efficiency and performance via 2 techniques. First, we employ a light-weight compression framework with awareness of register value similarity. It is coupled with a group-based write driver control to mitigate the high energy overhead caused by STT-RAM writes. Second, to address the long write latency overhead of STT-RAM, we propose a centralized SRAM-based write buffer design to efficiently absorb STT-RAM writes with better buffer utilization, rather than the conventional design with distributed per-bank based write buffers. The experimental results show that our STT-RAM based register file design consumes only 37.4% energy over the SRAM baseline, while incurring only negligible performance degradation.

“Java Generics Are Turing Complete”, Grigore 2016

“Java Generics are Turing Complete”⁠, Radu Grigore (2016-05-17; backlinks):

This paper describes a reduction from the halting problem of Turing machines to subtype checking in Java. It follows that subtype checking in Java is undecidable, which answers a question posed by Kennedy and Pierce in 2007. It also follows that Java’s type checker can recognize any recursive language, which improves a result of Gil and Levy from 2016. The latter point is illustrated by a parser generator for fluent interfaces.

“On Having No Head: Cognition throughout Biological Systems”, Baluška & Levin 2016

“On Having No Head: Cognition throughout Biological Systems”⁠, František Baluška, Michael Levin (2016; backlinks):

The central nervous system (CNS) underlies memory, perception, decision-making, and behavior in numerous organisms. However, neural networks have no monopoly on the signaling functions that implement these remarkable algorithms. It is often forgotten that neurons optimized cellular signaling modes that existed long before the CNS appeared during evolution, and were used by somatic cellular networks to orchestrate physiology, embryonic development, and behavior. Many of the key dynamics that enable information processing can, in fact, be implemented by different biological hardware. This is widely exploited by organisms throughout the tree of life. Here, we review data on memory, learning, and other aspects of cognition in a range of models, including single celled organisms, plants, and tissues in animal bodies. We discuss current knowledge of the molecular mechanisms at work in these systems, and suggest several hypotheses for future investigation. The study of cognitive processes implemented in aneural contexts is a fascinating, highly interdisciplinary topic that has many implications for evolution, cell biology, regenerative medicine, computer science, and synthetic bioengineering.

“Brainless but Multi-Headed: Decision Making by the Acellular Slime Mould Physarum Polycephalum”, Beekman & Latty 2015

2015-beekman.pdf: “Brainless but Multi-Headed: Decision Making by the Acellular Slime Mould Physarum polycephalum”⁠, Madeleine Beekman, Tanya Latty (2015-11-20; biology; backlinks):

• Can you make decisions if you are brainless?

• Here we use the acellular slime mould P. polycephalum to study decision making.

• We use foraging and network construction as experimental paradigms.

• Our work reveals the underlying basic mechanisms that organisms use to make decisions.

• We think that the slime mould can be developed further to function as a “model brain”.

Because of its peculiar biology and the ease with which it can be cultured, the acellular slime mould Physarum polycephalum has long been a model organism in a range of disciplines. Due to its macroscopic, syncytial nature, it is no surprise that it has been a favourite amongst cell biologists. Its inclusion in the experimental tool kit of behavioural ecologists is much more recent. These recent studies have certainly paid off. They have shown that, for an organism that lacks a brain or central nervous system, P. polycephalum shows rather complex behaviour. For example, it is capable of finding the shortest path through a maze, it can construct networks as efficient as those designed by humans, it can solve computationally difficult puzzles, it makes multi-objective foraging decisions, it balances its nutrient intake and it even behaves irrationally. Are the slime mould’s achievements simply “cute”, worthy of mentioning in passing but nothing to take too seriously? Or do they hint at the fundamental processes underlying all decision making? We will address this question after reviewing the decision-making abilities of the slime mould.

[Keywords: acellular slime mould, decision-making, foraging decisions, optimal foraging, trade-offs]

“Profiling a Warehouse-scale Computer”, Kanev et al 2015

2015-kanev.pdf#google: “Profiling a warehouse-scale computer”⁠, Svilen Kanev, Juan Pablo Darago, Kim M. Hazelwood, Parthasarathy Ranganathan, Tipp J. Moseley, Gu-Yeon Wei, et al (2015-06-01):

With the increasing prevalence of warehouse-scale (WSC) and cloud computing, understanding the interactions of server applications with the underlying microarchitecture becomes ever more important in order to extract maximum performance out of server hardware. To aid such understanding, this paper presents a detailed microarchitectural analysis of live datacenter jobs, measured on more than 20,000 Google machines over a three year period, and comprising thousands of different applications.

We first find that WSC workloads are extremely diverse, breeding the need for architectures that can tolerate application variability without performance loss. However, some patterns emerge, offering opportunities for co-optimization of hardware and software. For example, we identify common building blocks in the lower levels of the software stack. This “datacenter tax” can comprise nearly 30% of cycles across jobs running in the fleet, which makes its constituents prime candidates for hardware specialization in future server systems-on-chips. We also uncover opportunities for classic microarchitectural optimizations for server processors, especially in the cache hierarchy. Typical workloads place substantial stress on instruction caches and prefer memory latency over bandwidth. They also stall cores often, but compute heavily in bursts. These observations motivate several interesting directions for future warehouse-scale computers.

“Scalability! But at What COST?”, McSherry et al 2015

2015-mcsherry.pdf: “Scalability! But at what COST?”⁠, Frank McSherry, Michael Isard, Derek G. Murray (2015-05; backlinks):

We offer a new metric for big data platforms, COST, or the Configuration that Outperforms a Single Thread. The COST of a given platform for a given problem is the hardware configuration required before the platform outperforms a competent single-threaded implementation. COST weighs a system’s scalability against the overheads introduced by the system, and indicates the actual performance gains of the system, without rewarding systems that bring substantial but parallelizable overheads.

We survey measurements of data-parallel systems [for graph processing] recently reported in SOSP and OSDI, and find that many systems have either a surprisingly large COST, often hundreds of cores, or simply underperform one thread for all of their reported configurations.

“Antikernel: A Decentralized Secure Hardware-software Operating System Architecture”, Zonenberg 2015

2015-zonenberg.pdf: “Antikernel: A decentralized secure hardware-software operating system architecture”⁠, Andrew D. Zonenberg (2015-04-01):

[Paper⁠; see also exokernel⁠, capability-based security⁠, end-to-end principle] Security of monolithic kernels, and even microkernels, relies on a large and complex body of code (including both software and hardware components) being entirely bug-free. Most contemporary operating systems can be completely compromised by a bug anywhere in this codebase, from the network stack to the CPU pipeline’s handling of privilege levels, regardless of whether a particular application uses that feature or not. Even formally verified software is vulnerable to failure when the hardware, or the hardware-software interface, has not been verified.

This thesis describes Antikernel, a novel operating system architecture consisting of both hardware and software components and designed to be fundamentally more secure than the existing state of the art. In order to make formal verification easier, and improve parallelism, the Antikernel system is highly modular and consists of many independent hardware state machines (one or more of which may be a general-purpose CPU running application or systems software) connected by a packet-switched network-on-chip (NoC).

The Antikernel architecture is unique in that there is no “all-powerful” software which has the ability to read or modify arbitrary data on the system, gain low-level control of the hardware, etc. All software is unprivileged; the concept of “root” or “kernel mode” simply does not exist so there is no possibility of malicious software achieving such capabilities.

The prototype Antikernel system was written in a mixture of Verilog, C, and MIPS assembly language for the actual operating system, plus a large body of C++ in debug/​​support tools which are used for development but do not actually run on the target system. The prototype was verified with a combination of simulation (Xilinx ISim), formal model checking (using the MiniSAT solver integrated with yosys), and hardware testing (using a batch processing cluster consisting of Xilinx Spartan-3A, Spartan-6, Artix-7, and Kintex-7 FPGAs).

“Machine Teaching: an Inverse Problem to Machine Learning and an Approach Toward Optimal Education”, Zhu 2015

2015-zhu.pdf: “Machine Teaching: an Inverse Problem to Machine Learning and an Approach Toward Optimal Education”⁠, Xiaojin Zhu (2015-01-01; ai; backlinks):

I draw the reader’s attention to machine teaching, the problem of finding an optimal training set given a machine learning algorithm and a target model. In addition to generating fascinating mathematical questions for computer scientists to ponder, machine teaching holds the promise of enhancing education and personnel training. The Socratic dialogue style aims to stimulate critical thinking.

[See also Cakmak & Lopes 2012⁠; Huang et al 2017⁠; Brown & Niekum 2019⁠.]

“An Interview With Fred Brooks”, Brooks & Shustek 2015

2015-brooks.pdf: “An Interview with Fred Brooks”⁠, Fred Brooks, Len Shustek (2015-01-01):

ACM Fellow and A.M. Turing Award recipient Fred Brooks reflects on his career.

“What Are Weird Machines?”, Bratus 2015

“What are Weird Machines?”⁠, Sergey Bratus (2015; backlinks):

The expression “weird machines” was first used in the RSS 2009 talk⁠. It referred to state-of-the-art exploitation as finding and programming an execution model (a machine, such as a virtual automaton) within the target via crafted inputs. It was soon extended to other methods of reliably or probabilistically influencing the target’s state. A compressed version of that original talk was given at the Chaos Computing Congress 27c3 [slides]⁠, [video]⁠.

The concept was further elaborated in Exploitation and State Machines by Thomas Dullien / Halvar Flake at Infiltrate 2011, Heap Exploitation Abstraction by Example by Census Labs at OWASP 2012, and others. A historical sketch can be found in From Buffer Overflows to “Weird Machines” by Bratus et al 2011

Effort is underway to produce formal descriptions of weird machine classes in various computing environments. Thomas Dullien’s 2017 paper Weird machines, exploitability, and provable unexploitability is the most notable recent development (see Formalisms below). The LangSec effort is aimed at describing and eliminating broad classes of input-related bugs and associated weird machines.

“Kadupul: Livin’ on the Edge With Virtual Currencies and Time-Locked Puzzles”, Skjegstad et al 2014

“Kadupul: Livin’ on the Edge with Virtual Currencies and Time-Locked Puzzles”⁠, Magnus Skjegstad, Anil Madhavapeddy, Jon Crowcroft (2014-12-15; backlinks):

Devices connected to the Internet today have a wide range of local communication channels available, such as wireless Wifi, Bluetooth or NFC, as well as wired backhaul. In densely populated areas it is possible to create heterogeneous, multihop communication paths using a combination of these technologies, and often transmit data with lower latency than via a wired Internet connection. However, the potential for sharing meshed wireless radios in this way has never been realised due to the lack of economic incentives to do so on the part of individual nodes.

In this paper, we explore how virtual currencies such as Bitcoin might be used to provide an end-to-end incentive scheme to convince forwarding nodes that it is profitable to send packets on via the lowest latency mechanism available. Clients inject a small amount of money to transmit a datagram, and forwarding engines compete to solve a time-locked puzzle that can be claimed by the node that delivers the result in the lowest latency. This approach naturally extends congestion control techniques to a surge pricing model when available bandwidth is low. We conclude by discussing several latency-sensitive applications that would benefit for this, such as video streaming and local augmented reality systems.

“Braid Is Undecidable”, Hamilton 2014

“Braid is undecidable”⁠, Linus Hamilton (2014-12-02; backlinks):

Braid is a 2008 puzzle game centered around the ability to reverse time. We show that Braid can simulate an arbitrary computation. Our construction makes no use of Braid’s unique time mechanics, and therefore may apply to many other video games.

We also show that a plausible “bounded” variant of Braid lies within 2-EXPSPACE. Our proof relies on a technical lemma about Turing machines which may be of independent interest. Namely, define a braidlike Turing machine to be a Turing machine that, when it writes to the tape, deletes all data on the tape to the right of the head. We prove that deciding the behavior of such a machine lies in EXPSPACE.

“Computing's Energy Problem (and What We Can Do about It)”, Horowitz 2014

2014-horowitz.pdf: “Computing's Energy Problem (and what we can do about it)”⁠, Mark Horowitz (2014-02-09):

Our challenge is clear: The drive for performance and the end of voltage scaling have made power, and not the number of transistors, the principal factor limiting further improvements in computing performance. Continuing to scale compute performance will require the creation and effective use of new specialized compute engines, and will require the participation of application experts to be successful. If we play our cards right, and develop the tools that allow our customers to become part of the design process, we will create a new wave of innovative and efficient computing devices.

1. Introduction
2. Processor Scaling
3. Technology to the Rescue?
4. The Limits of Parallelism
5. Don’t Forget the Memory Energy
6. Gaining Efficiency through Specialization
7. Tools for Enabling Design
8. Conclusion

“Bloom Filter Applications in Network Security: A State-of-the-art Survey”, Geravand & Ahmadi 2013

2013-geravand.pdf: “Bloom filter applications in network security: A state-of-the-art survey”⁠, Shahabeddin Geravand, Mahmood Ahmadi (2013-12-24):

Undoubtedly, dealing with security issues is one of the most important and complex tasks various networks face today. A large number of security algorithms have been proposed to enhance security in various types of networks.

Many of these solutions are either directly or indirectly based on Bloom filters (BF), a space-efficient and time-efficient probabilistic data structure introduced by Burton Bloom in 1970. Obviously, Bloom filters and their variants are getting more and more consideration in network security area.

This paper provides an up-to-date survey of the application of BFs and their variants to improve performance of the approaches proposed to address security problems with different types of networks.

“Algorithmic Progress in Six Domains”, Grace 2013

2013-grace.pdf#miri: “Algorithmic Progress in Six Domains”⁠, Katja Grace (2013-12-09; ai /​ ​scaling⁠, economics /​ ​experience-curve; backlinks):

We examine evidence of progress in 6 areas of algorithms research [SAT, chess+Go, factoring, physics simulations, linear programming+scheduling, machine learning], with an eye to understanding likely algorithmic trajectories after the advent of artificial general intelligence. Many of these areas appear to experience fast improvement, though the data are often noisy. For tasks in these areas, gains from algorithmic progress have been roughly 50 to 100% as large as those from hardware progress. Improvements tend to be incremental, forming a relatively smooth curve on the scale of years.

[See also “The International SAT Solver Competitions”⁠, Järvisalo et al 2012; “A Time Leap Challenge for SAT Solving”⁠, Fichte et al 2020]

“What It Takes to Run Stack Overflow”, Craver 2013

“What it takes to run Stack Overflow”⁠, Nick Craver (2013-11-22; backlinks):

I like to think of Stack Overflow as running with scale but not at scale. By that I meant we run very efficiently, but I still don’t think of us as “big”, not yet…We like to call it magic, other people call it “multiple servers with multi-core processors”—but we’ll stick with magic. Here’s what runs the Stack Exchange network in that data center:

• 4 MS SQL Servers
• 11 IIS Web Servers
• 2 Redis Servers
• 3 Tag Engine servers (anything searching by tag hits this, eg. /​​​questions/​​​tagged/​​​c++)
• 3 Elasticsearch servers
• 2 Load balancers (HAProxy)
• 2 Networks (each a Nexus 5596 + Fabric Extenders)
• 2 Cisco 5525-X ASAs (think Firewall)
• 2 Cisco 3945 Routers

…Performance is a feature, a very important feature to us. The main page loaded on all of our sites is the question page, affectionately known as Question/​​Show (its route name) internally. On November 12^th, that page rendered in an average of 28 milliseconds. While we strive to maintain 50ms, we really try and shave every possible millisecond off your pageload experience. All of our developers are certifiably anal curmudgeons when it comes to performance, so that helps keep times low as well. Here are the other top hit pages on SO, average render time on the same 24 hour period as above:

• Question/​​Show: 28 ms (29.7 million hits)
• User Profiles: 39 ms (1.7 million hits)
• Question List: 78 ms (1.1 million hits)
• Home page: 65 ms

…It’s definitely worth noting that these servers run at very low utilization. Those web servers average between 5–15% CPU, 15.5 GB of RAM used and 20–40 Mb/​​s network traffic. The SQL servers average around 5–10% CPU, 365 GB of RAM used, and 100–200 Mb/​​s of network traffic.

…The primary reason the utilization is so low is efficient code…Now that we know how Stack Overflow performs on its current hardware, next time we can see why we don’t run in the cloud.

“Intelligence Explosion Microeconomics”, Yudkowsky 2013

2013-yudkowsky.pdf#miri: “Intelligence Explosion Microeconomics”⁠, Eliezer Yudkowsky (2013-09-13; ai /​ ​scaling⁠, economics /​ ​experience-curve; backlinks):

I. J. Good’s thesis of the “intelligence explosion” states that a sufficiently advanced machine intelligence could build a smarter version of itself, which could in turn build an even smarter version, and that this process could continue to the point of vastly exceeding human intelligence. As Sandberg 2010 correctly notes, there have been several attempts to lay down return on investment formulas intended to represent sharp speedups in economic or technological growth, but very little attempt has been made to deal formally with Good’s intelligence explosion thesis as such.

I identify the key issue as returns on cognitive reinvestment—the ability to invest more computing power, faster computers, or improved cognitive algorithms to yield cognitive labor which produces larger brains, faster brains, or better mind designs. There are many phenomena in the world which have been argued to be evidentially relevant to this question, from the observed course of hominid evolution, to Moore’s Law, to the competence over time of machine chess-playing systems, and many more. I go into some depth on some debates which then arise on how to interpret such evidence. I propose that the next step in analyzing positions on the intelligence explosion would be to formalize return on investment curves, so that each stance can formally state which possible micro-foundations they hold to be falsified by historical observations. More generally I pose multiple open questions of “returns on cognitive reinvestment” or “intelligence explosion microeconomics.” Although such questions have received little attention thus far, they seem highly relevant to policy choices affecting outcomes for Earth-originating intelligent life.

“Machine Teaching for Bayesian Learners in the Exponential Family”, Zhu 2013

“Machine Teaching for Bayesian Learners in the Exponential Family”⁠, Xiaojin Zhu (2013-06-20; backlinks):

What if there is a teacher who knows the learning goal and wants to design good training data for a machine learner? We propose an optimal teaching framework aimed at learners who employ Bayesian models. Our framework is expressed as an optimization problem over teaching examples that balance the future loss of the learner and the effort of the teacher. This optimization problem is in general hard. In the case where the learner employs conjugate exponential family models, we present an approximate algorithm for finding the optimal teaching set. Our algorithm optimizes the aggregate sufficient statistics, then unpacks them into actual teaching examples. We give several examples to illustrate our framework.

“Robust Soldier Crab Ball Gate”, Gunji et al 2012

“Robust Soldier Crab Ball Gate”⁠, Yukio-Pegio Gunji, Yuta Nishiyama, Andrew Adamatzky (2012-04-08; backlinks):

Soldier crabs Mictyris guinotae exhibit pronounced swarming behaviour. The swarms of the crabs tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.

“The International SAT Solver Competitions”, Järvisalo et al 2012

2012-jarvisalo.pdf: “The International SAT Solver Competitions”⁠, Matti Järvisalo, Daniel Le Berre, Olivier Roussel, Laurent Simon (2012-03-15; ai⁠, economics /​ ​experience-curve):

The International SAT Solver Competition is today an established series of competitive events aiming at objectively evaluating the progress in state-of-the-art procedures for solving Boolean satisfiability (SAT) instances.

Over the years, the competitions have substantially contributed to the fast progress in SAT solver technology that has made SAT a practical success story of computer science. This short article provides an overview of the SAT solver competitions.

“Correspondences Regarding Cryptography between John Nash and the NSA [typeset Version]”, Nash & Rosulek 2012

1955-nash-typeset.pdf: “Correspondences Regarding Cryptography between John Nash and the NSA [typeset version]”⁠, John Nash, Mike Rosulek (2012-02-20; backlinks):

In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA¹, have been transcribed and typeset in this document. [Typeset by Mike Rosulek: Department of Computer Science, University of Montana, mikero@cs.umt.edu]

“National Cryptologic Museum Opens New Exhibit on Dr. John Nash”, NSA 2012

“National Cryptologic Museum Opens New Exhibit on Dr. John Nash”⁠, NSA (2012-01-27; backlinks):

The National Cryptologic Museum’s newest exhibit, “An Inquisitive Mind: John Nash Letters”, features copies of correspondence between Dr. Nash and the National Security Agency (NSA) from the 1950s when he was developing his ideas on an encryption-decryption machine.

At the height of his career in mathematics, Dr. Nash wrote a series of letters to NSA, proposing ideas for such a machine. While the agency acknowledged his ideas, they were never adopted. The letters were preserved with NSA’s analysis in a collection of unsolicited correspondence received in 1955.

The unclassified letters and the agency’s analysis, portions of which were classified, remained protected in NSA’s records center until 2011, when the entire collection was reviewed and declassified. The entire collection is being formally accessioned to the National Archives and Records Administration and will be available for public viewing later this year.

Copies of Nash’s letters to NSA are on display at the National Cryptologic Museum with complete copies available for review in the museum’s library and on the museum’s web page.

“A Brief History of NP-Completeness, 1954–2012”, Johnson 2012

2012-johnson.pdf: “A Brief History of NP-Completeness, 1954–2012”⁠, David S. Johnson (2012-01-01; backlinks):

The year 2012 marks the 40^th anniversary of the publication of the influential paper “Reducibility among combinatorial problems” by Richard Karp. This paper was the first to demonstrate the wide applicability of the concept now known as NP-completeness, which had been introduced the previous year by Stephen Cook and Leonid Levin, independently. 2012 also marks the 100^th anniversary of the birth of Alan Turing, whose invention of what is now known as the “Turing machine” underlay that concept. In this chapter, I shall briefly sketch the history and pre-history of NP-completeness (with pictures), and provide a brief personal survey of the developments in the theory over the last 40 years and their impact (or lack thereof) on the practice and theory of optimization. I assume the reader is familiar with the basic concepts of NP-completeness, P, and NP, although I hope the story will still be interesting to those with only a fuzzy recollection of the definitions.

“STEPS Toward Expressive Programming Systems: "A Science Experiment"”, Ohshima et al 2012-page-2

“STEPS Toward Expressive Programming Systems: "A Science Experiment"”⁠, Yoshiki Ohshima, Dan Amelang, Ted Kaehler, Bert Freudenberg, Aran Lunzer, Alan Kay⁠, Ian Piumarta, Takashi Yamamiya, et al (2012; design⁠, philosophy; backlinks):

[Technical report from a research project aiming at writing a GUI OS in 20k LoC; tricks include ASCII art networking DSLs & generic optimization for text layout⁠, which lets them implement a full OS, sound, GUI desktops, Internet networking & web browsers, a text/​​document editor etc, all in less lines of code that most OSes need for small parts of any of those.]

…Many software systems today are made from millions to hundreds of millions of lines of program code that is too large, complex and fragile to be improved, fixed, or integrated. (One hundred million lines of code at 50 lines per page is 5000 books of 400 pages each! This is beyond human scale.) What if this could be made literally 1000× smaller—or more? And made more powerful, clear, simple and robust?…The ’STEPS

STEPS Aims At ‘Personal Computing’—STEPS takes as its prime focus the dynamic modeling of ‘personal computing’ as most people think of it…word processor, spreadsheet, Internet browser, other productivity SW; User Interface and Command Listeners: windows, menus, alerts, scroll bars and other controls, etc.; Graphics and Sound Engine: physical display, sprites, fonts, compositing, rendering, sampling, playing; Systems Services: development system, database query languages, etc.; Systems Utilities: file copy, desk accessories, control panels, etc.; Logical Level of OS: eg. file management, Internet, and networking facilities, etc.; Hardware Level of OS: eg. memory manager, process manager, device drivers, etc.

“Circadian Patterns of Wikipedia Editorial Activity: A Demographic Analysis”, Yasseri et al 2011

“Circadian patterns of Wikipedia editorial activity: A demographic analysis”⁠, Taha Yasseri, Róbert Sumi, János Kertész (2011-09-08; wikipedia; backlinks):

Wikipedia (WP) as a collaborative, dynamical system of humans is an appropriate subject of social studies. Each single action of the members of this society, i.e. editors, is well recorded and accessible. Using the cumulative data of 34 Wikipedias in different languages, we try to characterize and find the universalities and differences in temporal activity patterns of editors. Based on this data, we estimate the geographical distribution of editors for each WP in the globe. Furthermore we also clarify the differences among different groups of WPs, which originate in the variance of cultural and social features of the communities of editors.

“A Cross-Language Perspective On Speech Information Rate”, Pellegrino et al 2011

2011-pellegrino.pdf: “A Cross-Language Perspective On Speech Information Rate”⁠, François Pellegrino, Christophe Coupé, Egidio Marsico (2011-09; psychology; backlinks):

This article is a cross-linguistic investigation of the hypothesis that the average information rate conveyed during speech communication results from a trade-off between average information density and speech rate. The study, based on seven languages, shows a negative correlation between density and rate, indicating the existence of several encoding strategies. However, these strategies do not necessarily lead to a constant information rate. These results are further investigated in relation to the notion of syllabic complexity.

“Why Philosophers Should Care About Computational Complexity”, Aaronson 2011

“Why Philosophers Should Care About Computational Complexity”⁠, Scott Aaronson (2011-08-08; ai⁠, philosophy /​ ​epistemology⁠,  /​ ​logic⁠,  /​ ​mind⁠, statistics /​ ​decision; backlinks):

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory—the field that studies the resources (such as time, space, and randomness) needed to solve computational problems—leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.

“Notes on a New Philosophy of Empirical Science”, Burfoot 2011

“Notes on a New Philosophy of Empirical Science”⁠, Daniel Burfoot (2011-04-28; statistics /​ ​bias; backlinks):

This book presents a methodology and philosophy of empirical science based on large scale lossless data compression. In this view a theory is scientific if it can be used to build a data compression program, and it is valuable if it can compress a standard benchmark database to a small size, taking into account the length of the compressor itself. This methodology therefore includes an Occam principle as well as a solution to the problem of demarcation. Because of the fundamental difficulty of lossless compression, this type of research must be empirical in nature: compression can only be achieved by discovering and characterizing empirical regularities in the data. Because of this, the philosophy provides a way to reformulate fields such as computer vision and computational linguistics as empirical sciences: the former by attempting to compress databases of natural images, the latter by attempting to compress large text databases. The book argues that the rigor and objectivity of the compression principle should set the stage for systematic progress in these fields. The argument is especially strong in the context of computer vision, which is plagued by chronic problems of evaluation.

The book also considers the field of machine learning. Here the traditional approach requires that the models proposed to solve learning problems be extremely simple, in order to avoid overfitting. However, the world may contain intrinsically complex phenomena, which would require complex models to understand. The compression philosophy can justify complex models because of the large quantity of data being modeled (if the target database is 100 Gb, it is easy to justify a 10 Mb model). The complex models and abstractions learned on the basis of the raw data (images, language, etc) can then be reused to solve any specific learning problem, such as face recognition or machine translation.

“Exascale Computing: Technical Challenges”, Yelick 2011

2011-yelick.pdf: “Exascale Computing: Technical Challenges”⁠, Kathy Yelick (2011-01-01; backlinks)

“Google-Wide Profiling: A Continuous Profiling Infrastructure for Data Centers”, Tune et al 2010

2010-ren.pdf#google: “Google-Wide Profiling: A Continuous Profiling Infrastructure for Data Centers”⁠, Gang Ren; Tune, E.; Moseley, T.; Yixin Shi; Rus, S.; Hundt, R. (2010-08-19):

Google-Wide Profiling (GWP), a continuous profiling infrastructure for data centers, provides performance insights for cloud applications. With negligible overhead, GWP provides stable, accurate profiles and a datacenter-scale tool for traditional performance analyses. Furthermore, GWP introduces novel applications of its profiles, such as application-platform affinity measurements and identification of platform-specific, microarchitectural peculiarities.

“New Strategy of Lossy Text Compression”, Al-Dubaee & Ahmad 2010

2010-aldubaee.pdf: “New Strategy of Lossy Text Compression”⁠, Shawki A. Al-Dubaee, Nesar Ahmad (2010-08-05):

This paper proposes a new strategy that is based on the signal processing tools applied to text compression of files namely, the wavelet transform and the Fourier transform⁠.

The influence of compression size and threshold of wavelet filters and the Fourier transform as well as 2 parameters: families of wavelet filters and decomposition levels, on compression factor of text files are investigated. The experimental results are shown that the wavelet and the Fourier transforms are suitable for lossy text compression with non-stationary text signal files. In addition, the Fourier transform is the most suitable with files which have same characters such as aaa.txt and aaaa.txt files. However, the results of wavelet and Fourier transforms are lossless text compression with stationary text signal files (aaa.txt and aaaa.txt files).

This research also represents a step forwards dealing with both images and text compression ie. multimedia compression.

[Keywords: Wavelet transforms, Fourier transforms, ASCII, lossy, text compression]

“You're Doing It Wrong: Think You've Mastered the Art of Server Performance? Think Again.”, Kamp 2010

“You're Doing It Wrong: Think you've mastered the art of server performance? Think again.”⁠, Poul-Henning Kamp (2010-06-11; backlinks):

[Discussion of optimization Poul-Henning Kamp (PHK) made to Varnish⁠, switching to an obscurer data structure which has better cache performance. This switch singlehandedly made a highly-optimized piece of software a good third faster.

Varnish is a web server technology which is used to store millions or billions of web pages/​​files in RAM to serve them ultra-fast, instead of falling back to a regular web server which may need to pull a file off the disk or use laborious computations to create the necessary web page. This is a straightforward high-volume task which should be bottlenecked on network and CPU—copying parts of RAM to the network as fast as possible.

PHK observed that Varnish server CPUs were not a bottleneck, and almost entirely idle. Why? Because it was spending most of its time tracking what files were in RAM, to make sure the copies weren’t too old & obsolete. This tracking was conveniently & efficiently implemented as a binary heap⁠.

Unfortunately, a Varnish server wants to spend all its memory on the actual files it’s there to send, forcing much of the binary heap to be stashed on disk. This is bad because the binary heap assumes that all of it is in memory and optimizes for number of queries, spreading itself across a lot of memory—except because it is getting pushed out to disk, that means that each lookup may require going out to disk. So while the binary heap requires the minimum number of queries to figure out what objects are obsolete, each query is a worst-case query, unexpectedly taking milliseconds or entire seconds!

The solution is to take a binary heap and rearrange it into a “B-heap” to keep nearby entries on the same part of disk, instead of scattered across the disk. That way, when Varnish is forced to go out to disk to check obsoleteness, it at least only has to do a few queries on a single part of the disk which can be read en masse, and can get back to useful work more quickly.]

“BatesTalk”, Bates 2010

2010-bates.pdf: “BatesTalk”⁠, Joseph Bates (2010-01-01; anime; backlinks)

“Implications of the Turing Completeness of Reaction-diffusion Models, Informed by GPGPU Simulations on an XBox 360: Cardiac Arrhythmias, Re-entry and the Halting Problem”, Scarle 2009

“Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: Cardiac arrhythmias, re-entry and the halting problem”⁠, Simon Scarle (2009-08-01; backlinks):

In the arsenal of tools that a computational modeler can bring to bear on the study of cardiac arrhythmias the most widely used and arguably the most successful is that of an excitable medium, a special case of a reaction-diffusion model. These are used to simulate the internal chemical reactions of a cardiac cell and the diffusion of their membrane voltages. Via a number of different methodologies it has previously been shown that reaction-diffusion systems are at multiple levels Turing complete. That is, they are capable of computation in the same manner as a universal Turing machine. However, all such computational systems are subject to a limitation known as the Halting problem.

By constructing a universal logic gate using a cardiac cell model, we highlight how the Halting problem therefore could limit what it is possible to predict about cardiac tissue, arrhythmias and re-entry. All simulations for this work were carried out on the GPU of an XBox 360 development console, and we also highlight the great gains in computational power and efficiency produced by such general purpose processing on a GPU for cardiac simulations.

[Keywords: heart, re-entry, cardiac arrhythmias, excitable media, halting problem, GPGPU]

“De-anonymizing Social Networks”, Narayanan & Shmatikov 2009

2009-narayanan.pdf: “De-anonymizing Social Networks”⁠, Arvind Narayanan, Vitaly Shmatikov (2009-05-17; backlinks):

Operators of online social networks are increasingly sharing potentially sensitive information about users and their relationships with advertisers, application developers, and data-mining researchers. Privacy is typically protected by anonymization, ie., removing names, addresses, etc.

We present a framework for analyzing privacy and anonymity in social networks and develop a new re-identification algorithm targeting anonymized social-network graphs. To demonstrate its effectiveness on real-world networks, we show that a third of the users who can be verified to have accounts on both Twitter, a popular microblogging service, and Flickr⁠, an online photo-sharing site, can be re-identified in the anonymous Twitter graph with only a 12% error rate.

Our de-anonymization algorithm is based purely on the network topology, does not require creation of a large number of dummy “sybil” nodes, is robust to noise and all existing defenses, and works even when the overlap between the target network and the adversary’s auxiliary information is small.

“Producing Wrong Data Without Doing Anything Obviously Wrong!”, Mytkowicz et al 2009

2009-mytkowicz.pdf: “Producing Wrong Data Without Doing Anything Obviously Wrong!”⁠, Todd Mytkowicz, Amer Diwan, Matthias Hauswirth, Peter F. Sweeney (2009-03-07; statistics /​ ​bias; backlinks):

[Previously, Blackwell 1998] This paper presents a surprising result: changing a seemingly innocuous aspect of an experimental setup can cause a systems researcher to draw wrong conclusions from an experiment. What appears to be an innocuous aspect in the experimental setup may in fact introduce a substantial bias in an evaluation. This phenomenon is called measurement bias in the natural and social sciences.

Our results demonstrate that measurement bias is substantial and commonplace in computer system evaluation. By significant we mean that measurement bias can lead to a performance analysis that either over-states an effect or even yields an incorrect conclusion. By commonplace we mean that measurement bias occurs in all architectures that we tried (Pentium 4, Core 2, and m5 O3CPU), both compilers that we tried (gcc and Intel’s C compiler), and most of the SPEC CPU2006 C programs. Thus, we cannot ignore measurement bias. Nevertheless, in a literature survey of 133 recent papers from ASPLOS, PACT, PLDI, and CGO, we determined that none of the papers with experimental results adequately consider measurement bias.

Inspired by similar problems and their solutions in other sciences, we describe and demonstrate two methods, one for detecting (causal analysis) and one for avoiding (setup randomization) measurement bias.

[Keywords: experimentation, measurement, performance, bias]

“Is There A Fourth Futamura Projection?”, Robert 2009

2009-gluck.pdf: “Is There A Fourth Futamura Projection?”⁠, Glueck Robert (2009-01-10)

“Harnessing Vision for Computation”, Changizi 2008

2008-changizi.pdf: “Harnessing Vision for Computation”⁠, Mark Changizi (2008-01-01; backlinks):

Might it be possible to harness the visual system to carry out artificial computations, somewhat akin to how DNA has been harnessed to carry out computation? I provide the beginnings of a research programme attempting to do this. In particular, new techniques are described for building ‘visual circuits’ (or ‘visual software’) using wire, NOT, OR, and AND gates in a visual modality such that our visual system acts as ‘visual hardware’ computing the circuit, and generating a resultant perception which is the output.

“What Every Programmer Should Know About Memory”, Drepper 2007

2007-drepper.pdf: “What Every Programmer Should Know About Memory”⁠, Ulrich Drepper (2007-11-12; anime; backlinks):

As CPU cores become increasingly faster, the limiting factor for most programs is now, and will be for some time, memory access. Hardware designers have come up with ever-more sophisticated memory-handling and memory-acceleration techniques—such as CPU caches—but these cannot work optimally without some help from the programmer. Unfortunately, neither the structure nor the cost of using the memory subsystem of a computer or the caches on CPU is well understood by most programmers. This paper explains the structure of memory subsystems in use on modern commodity hardware, illustrating why CPU caches were developed, how they work, and what programs should do to achieve optimal performance by utilizing them.

[Some parts are obsolete as of 2017.]

“History of Combinatorial Generation (The Art of Computer Programming: Volume 4: Pre-Fascicle 4B: Section 7.2.1.7)”, Knuth 2005

2005-knuth-taocp-v4-prefascicle4b.pdf: “History of Combinatorial Generation (The Art of Computer Programming: Volume 4: Pre-Fascicle 4B: Section 7.2.1.7)”⁠, Donald E. Knuth (2005-10-28)

“Toward a Broader View of Security Protocols”, Blaze 2004

“Toward a Broader View of Security Protocols”⁠, Matt Blaze (2004-03-06; backlinks):

This position paper initiates and advocates the study of “Human-Scale Security Protocols” as a core activity of computing and network security research. The Human-Scale Security Protocols (HSSP) project treats “human scale” security problems and protocols as a central part of computer science. Our aim is to identify, stimulate research on, analyze, and improve “non-traditional” protocols that might either have something to teach us or be susceptible to improvement via the techniques and tools of computer security. There are compelling security problems across a wide spectrum of areas that do not outwardly involve computers or electronic communication and yet are remarkably similar in structure to the systems computer scientists routinely study. Interesting and relevant problem spaces that computer security has traditionally ignored range from the very serious (preventing terrorists from subverting aviation security) to the trivial and personal (ensuring that a restaurant serves the same wine that was ordered and charged for).

“A Short History of Computational Complexity”, Fortnow et al 2003

2003-fortnow.pdf: “A Short History of Computational Complexity”⁠, Fortnow, Lance, Homer, Steve (2003-10-02; backlinks)

“Solving Real-World Linear Programs: A Decade and More of Progress”, Bixby 2002

2002-bixby.pdf: “Solving Real-World Linear Programs: A Decade and More of Progress”⁠, Robert E. Bixby (2002-02-01; ai⁠, economics /​ ​experience-curve):

This paper is an invited contribution to the 50^th anniversary issue of the journal Operations Research, published by the Institute of Operations Research and Management Science (INFORMS). It describes one person’s perspective on the development of computational tools for linear programming. The paper begins with a short personal history, followed by historical remarks covering the some 40 years of linear-programming developments that predate my own involvement in this subject. It concludes with a more detailed look at the evolution of computational linear programming since 1987.

…In this paper I have focused primarily on one issue, solving larger, more difficult linear programs faster. The numbers presented speak for themselves. 3 orders of magnitude in machine speed and 3 orders of magnitude in algorithmic speed add up to six orders of magnitude in solving power: A model that might have taken a year to solve 10 years ago can now solve in less than 30 seconds. Of course, no one waits 1 year to solve a model, at least no one I know. The real meaning of such an advance is much harder to measure in practice, but it is real nevertheless. There is no doubt that we now have optimization engines at our disposal that dwarf what was available only a few years ago, making possible the solution of real-world models once considered intractable, and opening up whole new domains of application.

How do these speed improvements fit into the overall picture of linear-programming practice? They are only a part of that picture, though an essential, enabling part. The pervasive availability of powerful, usable desktop computing, the availability of data to feed our models, and the emergence of algebraic modeling languages to represent our models have all combined with the underlying engines to make operations research and linear programming the powerful tools they are today. However, there are still important issues to be solved. In spite of all the advances, the application of linear programming remains primarily the domain of experts. The need for abstraction still stands as a hurdle between technology and solutions. While the existence of this hurdle is disconcerting, it is at least gratifying to know that the benefits from overcoming it are now greater than ever.

“The Wheel of Reincarnation”, Hardy 2002

“The Wheel of Reincarnation”⁠, Norman Hardy (2002; economics; backlinks):

[2002? Short technology essay based on Myer & Sutherland 1968 (!) discussing a perennial pattern in computing history dubbed the ‘Wheel of Reincarnation’ for how old approaches inevitably reincarnate as the exciting new thing: shifts between ‘local’ and ‘remote’ computing resources, which are exemplified by repeated cycles in graphical display technologies from dumb ‘terminals’ which display only raw pixels to smart devices which interpret more complicated inputs like text or vectors or finally fullblown programming languages which render specified images locally (eg. PostScript).

These cycles are driven by cost, latency, architectural simplicity, and available computing power.

The Wheel of Reincarnation paradigm has played out for computers as well, in shifts from local terminals attached to mainframes to PCs to smartphones to ‘cloud computing’. Similar cycles can play out with other techs like software configuration⁠.]

“Naked Objects: a Technique for Designing More Expressive Systems”, Pawson & Matthews 2001

2001-pawson.pdf: “Naked objects: a technique for designing more expressive systems”⁠, Richard Pawson, Robert Matthews (2001-12-01):

Naked objects is an approach to systems design in which core business objects show directly through to the user interface, and in which all interaction consists of invoking methods on those objects in the noun-verb style. One advantage of this approach is that it results in systems that are more expressive from the viewpoint of the user: they treat the user like a problem solver, not as merely a process-follower. Another advantage is that the 1:1 mapping between the user’s representation and the underlying model means that it is possible to auto-generate the former from the latter, which yields benefits to the development process. The authors have designed a Java-based, open source toolkit called Naked Objects which facilitates this style of development. This paper describes the design and operation of the toolkit and its application to the prototyping of a core business system. Some initial feedback from the project is provided, together with a list of future research directions both for the toolkit and for a methodology to apply the naked objects approach.

“On Proebsting's Law”, Scott 2001

2001-scott.pdf: “On Proebsting's Law”⁠, Kevin Scott (2001-03-01; anime⁠, economics /​ ​experience-curve; backlinks):

In 1965 Gordon Moore observed that the capacity of semiconductor ICs doubled every 18 to 24 months. This trend, now known as Moore’s Law, has held for over 25 years and is responsible for the exponential increase in microprocessor performance over this period. In 1998 Todd Proebsting made a similar-in-spirit, but altogether less optimistic observation about optimizing compilers. His observation, henceforth known as Proebsting’s Law⁠, is that improvements to compiler technology double the performance of typical programs every 18 years. Proebsting has suggested an experiment to evaluate the veracity of his observation. This paper presents the results of this experiment and some comments on what Proebsting’s Law portends for compiler research.

“Peopleware: Why Measure Performance”, DeMarco & Lister 2001

2001-demarco-peopleware-whymeasureperformance.pdf: “Peopleware: Why Measure Performance”⁠, Tom DeMarco, Timothy Lister (2001-01-01; dual-n-back; backlinks)

“It's the Latency, Stupid”, Cheshire 2001

“It's the Latency, Stupid”⁠, Stuart Cheshire (2001; dual-n-back; backlinks):

[Seminal essay explaining why the rollout of “broadband” home connections to replace 56k dialups had not improved regular WWW browsing as much as people expected: while broadband had greater throughput, it had similar (or worse) latency.

Because much of the wallclock time of any Internet connection is spent setting up and negotiating with the other end, and not that much is spent on the raw transfer of large numbers of bytes, the speedup is far smaller than one would expect by dividing the respective bandwidths.

Further, while bandwidth/​​throughput is easy to improve by adding more or higher-quality connections and can be patched elsewhere in the system by adding parallelism or upgrading parts or investing in data compression, the latency-afflicted steps are stubbornly serial, any time lost is physically impossible to retrieve, and many steps are inherently limited by the speed of light—more capacious connections quickly run into Amdahl’s law⁠, where the difficult-to-improve serial latency-bound steps dominate the overall task. As Cheshire summarizes it:]

1. Fact One: Making more bandwidth is easy.
2. Fact Two: Once you have bad latency you’re stuck with it.
3. Fact Three: Current consumer devices have appallingly bad latency.
4. Fact Four: Making limited bandwidth go further is easy.

…That’s the problem with communications devices today. Manufacturers say “speed” when they mean “capacity”. The other problem is that as far as the end-user is concerned, the thing they want to do is transfer large files quicker. It may seem to make sense that a high-capacity slow link might be the best thing for the job. What the end-user doesn’t see is that in order to manage that file transfer, their computer is sending dozens of little control messages back and forth. The thing that makes computer communication different from television is interactivity, and interactivity depends on all those little back-and-forth messages.

The phrase “high-capacity slow link” that I used above probably looked very odd to you. Even to me it looks odd. We’ve been used to wrong thinking for so long that correct thinking looks odd now. How can a high-capacity link be a slow link? High-capacity means fast, right? It’s odd how that’s not true in other areas. If someone talks about a “high-capacity” oil tanker, do you immediately assume it’s a very fast ship? I doubt it. If someone talks about a “large-capacity” truck, do you immediately assume it’s faster than a small sports car?

We have to start making that distinction again in communications. When someone tells us that a modem has a speed of 28.8 kbit/​​sec we have to remember that 28.8 kbit/​​sec is its capacity, not its speed. Speed is a measure of distance divided by time, and ‘bits’ is not a measure of distance.

I don’t know how communications came to be this way. Everyone knows that when you buy a hard disk you should check what its seek time is. The maximum transfer rate is something you might also be concerned with, but the seek time is definitely more important. Why does no one think to ask what a modem’s ‘seek time’ is? The latency is exactly the same thing. It’s the minimum time between asking for a piece of data and getting it, just like the seek time of a disk, and it’s just as important.

“LNCS 1796 - Time-Lock Puzzle With Examinable Evidence of Unlocking Time”, Mao 2000

2000-mao.pdf: “LNCS 1796 - Time-Lock Puzzle with Examinable Evidence of Unlocking Time”⁠, Wenbo Mao (2000-01-01; backlinks)

“Ultimate Physical Limits to Computation”, Lloyd 1999

“Ultimate physical limits to computation”⁠, Seth Lloyd (1999-08-13; backlinks):

Computers are physical systems: what they can and cannot do is dictated by the laws of physics. In particular, the speed with which a physical device can process information is limited by its energy and the amount of information that it can process is limited by the number of degrees of freedom it possesses. This paper explores the physical limits of computation as determined by the speed of light c, the quantum scale ℏ and the gravitational constant G. As an example, quantitative bounds are put to the computational power of an ‘ultimate laptop’ with a mass of one kilogram confined to a volume of one liter.

“Applications of Randomness in System Performance Measurement”, Blackwell 1998

“Applications of Randomness in System Performance Measurement”⁠, Trevor Leslie Blackwell (1998-05; statistics /​ ​bias):

This thesis presents and analyzes a simple principle for building systems: that there should be a random component in all arbitrary decisions. If no randomness is used, system performance can vary widely and unpredictably due to small changes in the system workload or configuration. This makes measurements hard to reproduce and less meaningful as predictors of performance that could be expected in similar situations.

To measure the sensitivity of non-randomized systems to slight configuration changes, we measured the variation in performance of both TCP  /​ ​ ​ ​IP and workstation memory systems as a result of “small” configuration perturbations. By “small”, we mean within the range over which things may change unintentionally due to other modifications being evaluated, or within the range of accuracy that an independent researcher could reasonably achieve.

For TCP/​​IP, changes of a few percent in link propagation delays and other parameters caused order of magnitude shifts in bandwidth allocation between competing connections. For memory systems, changes in the essentially arbitrary order in which functions were arranged in memory caused changes in runtime of tens of percent for single benchmarks, and of a few percent when averaged across a suite of benchmarks. In both applications the measured variability is larger than performance increases often reported for new improved designs, suggesting that many published measurements of the benefits of new schemes may be erroneous or at least irreproducible.

To make TCP/​​IP and memory systems measurable enough to make benchmark results meaningful and convincing, randomness must be added. Methods for adding randomness to conventional program linkers⁠, to linkers which try to optimize memory system performance by avoiding cache conflicts, and to TCP/​​IP are presented and analyzed. In all of the systems, various amounts of randomness can be added in many different places. We show how to choose reasonable amounts of randomness based on measuring configuration sensitivity, and propose specific recipes for randomizing TCP/​​IP and memory systems. Substantial reductions in the configuration sensitivity are demonstrated, making measurements much more robust and meaningful. The accuracy of the results increases with the number of runs and thus is limited only by the available computing resources.

When the overall performance of a system is strongly influenced by the worst case behavior, reducing the sensitivity of the system can also make it perform better. Using average waiting time as a metric, TCP/​​IP performance is shown to improve substantially when randomization is added to the sending host’s congestion window calculations. Although the improvements are less than those achieved by previously proposed schemes using randomized packet discard algorithms inside the network, the proposed modifications can be implemented entirely in the sending host and so can be deployed more easily.

…When arbitrary decisions are made deterministically based on small-scale properties of the system, the overall performance of the system is likely to be highly sensitive to slight changes in configuration, initial conditions, or the results of internal computations of the system itself. For such a system, the graph of performance as a function of one or more of its configuration parameters looks jagged, and a measurement with any given set of configuration parameters may not be representative. If past decisions can affect future decisions, the system may be chaotic, meaning that an arbitrarily small change in initial conditions can cause an arbitrarily large change in the behavior of the system.

Highly sensitive deterministic systems have 2 disadvantages. First, it is hard to make robust and reproducible measurements of them. These terms will be described formally below, but intuitively, if the system performs radically better or worse due to small changes in some aspect of the system, then any single measurement is a poor predictor of the performance that could be expected in general.

The second disadvantage of highly sensitive deterministic systems is that they are likely to fall into behavior patterns which repeat regularly on the small scale and result in poor overall performance on the large scale. For example, a memoryless resource allocator must decide to grant its resource to one user or another based only on the current set of requests. If there is no random input to its decision making process, it may persistently favor some users and starve others, resulting in poor overall performance.

To avoid extreme sensitivity, arbitrary decisions should be randomized. When randomness is added to highly sensitive systems and performance is reported as the distribution across a large number of individual measurements, we show that performance does not change radically with small changes in the initial conditions.

The following hypothetical example illustrates how extreme sensitivity leads to misleading results and incorrect design decisions. Consider the problem of deciding whether or not a particular compiler optimization improves performance (ie. reduces the runtime of the compiled program.) Suppose that the optimization eliminates some redundant instructions, thereby reducing the number of instruction execution cycles by 2%. The eliminated instructions reduce the sizes of some procedures, and (as will be shown in detail in Chapter 4), cache effects cause runtime to be highly sensitive to procedure sizes. Although in general the optimization would be expected to reduce memory system costs, suppose that changing cache conflicts cause it to increase memory system costs by 10% on the particular benchmark being used by the compiler developer. Thus a measurement would show an 8% performance decrease leading to a decision not to include the optimization in the compiler. Note that if another optimization is added which also affects procedure sizes, the memory system effects might be quite different.

“Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years”, Proebsting 1998

“Proebsting's Law: Compiler Advances Double Computing Power Every 18 Years”⁠, Todd Proebsting (1998; anime⁠, economics /​ ​experience-curve; backlinks):

I claim the following simple experiment supports this depressing claim. Run your favorite set of benchmarks with your favorite state-of-the-art optimizing compiler. Run the benchmarks both with and without optimizations enabled. The ratio of of those numbers represents the entirety of the contribution of compiler optimizations to speeding up those benchmarks. Let’s assume that this ratio is about 4× for typical real-world applications, and let’s further assume that compiler optimization work has been going on for about 36 years. These assumptions lead to the conclusion that compiler optimization advances double computing power every 18 years. QED.

This means that while hardware computing horsepower increases at roughly 60%/​​year, compiler optimizations contribute only 4%. Basically, compiler optimization work makes only marginal contributions.

Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena.

“Solved: The Ciphers In Book III Of Trithemius's Steganographia”, Reeds 1998

1998-reeds.pdf: “Solved: The Ciphers In Book III Of Trithemius's Steganographia”⁠, Jim Reeds (1998):

Book III of Trithemius’s Steganographia (written ca. 1500) contains hidden cipher messages within what is ostensibly a work on magic. After almost 500 years these cryptograms have been detected and solved. (Since 1606 it was known that similar ciphers were present in Books I and II.) As a result the Steganographia can no longer be regarded as one of the main early modern demonological treatises but instead stands unambiguously revealed as the first book-length treatment of cryptography in Europe.

[Keywords: Trithemius, Steganographia, history of cryptography.]

“Entropy of Natural Languages: Theory and Experiment”, Levitin & Reingold 1994

1994-levitin.pdf: “Entropy of natural languages: Theory and experiment”⁠, Lev B. Levitin, Zeev Reingold (1994-05-01):

The concept of the entropy of natural languages, first introduced by Shannon 1948 and its importance is discussed. A review of various known approaches to and results of previous studies of language entropy is presented. A new improved method for evaluation of both lower and upper bounds of the entropy of printed texts is developed. This method is a refinement of Shannon 1951’s prediction (guessing) method. The evaluation of the lower bound is shown to be a classical linear programming problem. Statistical analysis of the estimation of the bounds is given and procedures for the statistical treatment of the experimental data (including verification of statistical validity and statistical-significance) are elaborated. The method has been applied to printed Hebrew texts in a large experiment (1000 independent samples) in order to evaluate entropy and other information-theoretical characteristics of the Hebrew language. The results have demonstrated the efficiency of the new method: the gap between the upper and lower bounds of entropy has been reduced by a factor of 2.25 compared to the original Shannon approach. Comparison with other languages is given. Possible applications of the method are briefly discussed.

“Information and Secrecy: Vannevar Bush, Ultra, and the Other Memex”, Burke 1994

1994-burke-informationandsecrecyvannevarbushultrandtheothermemex.pdf: “Information and Secrecy: Vannevar Bush, Ultra, and the Other Memex”⁠, Colin Burke (1994-01-01)

“Building a Large Annotated Corpus of English: The Penn Treebank”, Marcus et al 1993

1993-marcus.pdf: “Building a Large Annotated Corpus of English: The Penn Treebank”⁠, Mitchell Marcus, Beatrice Santorini, Mary Ann Marcinkiewicz (1993-10-01; ai /​ ​scaling; backlinks):

In this paper, we review our experience with constructing one such large annotated corpus—the Penn Treebank, a corpus consisting of over 4.5 million words of American English. During the first three-year phase of the Penn Treebank Project (1989–1992), this corpus has been annotated for part-of-speech (POS) information. In addition, over half of it has been annotated for skeletal syntactic structure.

“Cosmetics As a Potential Source of Particulate Contamination in the Clean Room”, Hauenstein 1993

1993-hauenstein.pdf: “Cosmetics as a Potential Source of Particulate Contamination in the Clean Room”⁠, L. Ricks Hauenstein (1993; technology):

Since the early 1980’s, all major semiconductor manufacturers invoked the “no-cosmetics” policy. This had some severe psychological effects on the female workforce which comprised approximately 90% of the wafer fab employees. In the interest of business (as well as wafer yield), this policy was upheld. This paper discusses some of the psychological responses by the fab operators. Several experiments were performed which indicated that cosmetics presented a source of particulate contamination but at the same time cosmetics can prevent skin flaking. However, the use of cosmetics by both men and women could be detrimental to the cleanroom even when the personnel may not actually be wearing the cosmetics in the clean room. This paper is to raise the level of awareness to the problem of cosmetics in the clean room and to offer some clean room protocol procedures that can minimize and possibly eliminate much of the human contaminants. Cosmetics in the clean room is not restricted to the female workforce. Men are also guilty of using cosmetics while in the clean room. This paper examines this problem and suggests cleanroom guidelines.

Background: The space program requires 100% electronic uptime on all major systems. In 1985 one of the shuttle missions was scrubbed because mission guidelines did not allow lift off with only 4 of 5 computers operational. The cost of the aborted mission was in excess of $30^$10₁₉₈₅ million and the cost of the removal and replacement of the defective component was approximately $1,505,530^$500,000₁₉₈₅. Failure analysis of the shuttle component found corrosion of the semiconductor metallization as a result of human contamination (spittle, in this particular instance).¹⁴ Similar accounts are described by FAA computers and banking computers failing for similar defects in their CPU IC’s.

The space shuttle incidence has caused NASA and FAA to personally audit prime semiconductor contractors. They found that 1–3% of all semiconductor devices had some form of human contamination. Since human-related contamination is more of a reliability issue, military specs are now in place to require all microcircuits to be chemically analyzed for any on-die contaminants prior to sealing.

…The second task was to develop experiments that could be repeated as often as necessary to illustrate that cosmetics were a serious source of contamination. The experiment was simply having operators with and without cosmetics performing simple wafer handling chores: wafer inspections at an inspection station next to the Aeronca particle monitor. This test was repeated several times per week, using different operators with different skin types. Figures 2 and 3 summarize the results of this testing. Both men and women were tested across all 3 fabs. In Figure 2, women of all skin types generated more particles when not wearing makeup. This would seem normal since nearly all cosmetics (or, more specifically, make-up) has a moisturizer base which keeps the skin less dry in the harsh conditions of the clean room. The one exception is that women classified as having oily skin flaked about the same, with or without cosmetics. This is because the skin will not slough off as much since the skin has its own built in moisturizing system, called keratin¹⁷. Similarly, women with dark skin tend to have less dryness because of the excess skin pigmentation which also acts as a moisturizer.

…Even cosmetics that are used to protect the skin find their way to the microcircuit (or other products relating to clean rooms). In an unrelated experiment in which Advanced Micro Devices was in the process of developing a new site-wide wafer fab protocol spec, the training department began dry-runs of the series of classes involving the new, more rigid clean room procedures. One of the classes involved selected wafer fab operators and the purpose was to demonstrate the proper method to put on the clean room attire. However, the gloves were treated with a phosphorescent powder (the same type used by the police to “lift” fingerprints). Some of the older operators could feel the powder but they passed it off as being part of a new style of glove. After all the participants were in their proper clean room attire (including the gloves), the trainer discussed various protocol rules with the operators. About a half hour later the trainer informed everyone that the gloves had been lightly dusted. One by one, each person stood in front of a full length mirror while the trainer scanned their body with a black light. With few exceptions, there were yellow fingerprints allover their smocks as well on unprotected areas such as their faces and arms. This test was to illustrate that human contamination can find its way to the work area even with all possible protective measures in force.

…Many of the contaminants in cosmetics are harmless to the wafer fab. But as this paper has illustrated, most cosmetics of all types contain chemicals and compounds that can be devastating to semiconductor processing. The EDS illustrations of Figures 4 through 9 show an abundance of easily ionized elements with low 1^st ionization potential. The lower this potential, the easier it is for that element to combine with other elements. Also, Table 1 shows the common elements in body fluids (or skin tissue) which also have low first ionization potential. As in the case of the space shuttle where the defect was latent⁠, that is, it occurred after the device had been tested and was in the field, many of the defects caused by cosmetics can also be latent. It is these defects for which we have more concern. The immediate defects are usually caught at the manufacturer’s facility or even at the subsystem level. Most of the highly ionized metallic elements can cause immediate damage such as metal shorts, breakdowns in the oxides, threshold shifts, and various resistance changes.

…To illustrate the effects of cosmetics on the parametric values of the semiconductors, several wafers were contaminated with after shave, talc, eye liner, lipstick, blush, mascara residue, moisturizer, and skin flakes/​​hair…These are just a few of the types of parameter changes that can occur when cosmetics (and cosmetics on skin) come in contact with a semiconductor device in the clean room.

“An Empirical Study of the Reliability of UNIX Utilities”, Miller et al 1990

1990-miller.pdf: “An empirical study of the reliability of UNIX utilities”⁠, Barton P. Miller, Louis Fredriksen, Bryan So (1990):

Operating system facilities, such as the kernel and utility programs, are typically assumed to be reliable. In our recent experiments, we have been able to crash 25–33% of the utility programs on any version of UNIX that was tested. This report describes these tests and the program bugs that caused the crashes…The following section describes the tools we built to test the utilities. These tools include the fuzz (random character) generator, ptyjig (to test interactive utilities), and scripts to automate the testing process. Next, we will describe the tests we performed, giving the types of input we presented to the utilities. Results from the tests will follow along with an analysis of the results, including identification and classification of the program bugs that caused the crashes. The final section presents concluding remarks, including suggestions for avoiding the types of problems detected by our study and some commentary on the bugs we found. We include an Appendix with the user manual pages for fuzz and ptyjig.

“Separating Strings With Small Automata”, Robson 1989

1989-robson.pdf: “Separating strings with small automata”⁠, J. M. Robson (1989-02-27)

“Optimal Nonlinear Approximation”, DeVore et al 1989

1989-devore.pdf: “Optimal Nonlinear Approximation”⁠, Ronald A. DeVore, Ralph Howard, Charles Micchelli (1989):

We introduce a definition of nonlinear n-widths and then determine the n-widths of the unit ball of the Sobolev space W[^r^~p~]{.supsub} in L_q. We prove that in the sense of these widths the manifold of splines of fixed degree with n free knots is optimal for approximating functions in these Sobolev spaces.

“Hypertext '87: Keynote Address”, Dam 1988

1988-vandam.pdf: “Hypertext '87: keynote address”⁠, Andries van Dam (1988-07-01; design)

“Hypertext and the Oxford English Dictionary”, Raymond & Tompa 1988

1988-raymond.pdf: “Hypertext and the Oxford English dictionary”⁠, Darrel R. Raymond, Frank William Tompa (1988-07-01; design):

Hypertext databases can be produced by converting existing text documents to electronic form. The basic task in conversion is identification of fragments. We illustrate that this is not always a straightforward process with an analysis of the Oxford English Dictionary.

“A Differentiation Primitive for Extended Λ–calculus”, Flaherty 1988

1988-flaherty.pdf: “A differentiation primitive for extended λ–calculus”⁠, Terry Flaherty (1988-02-01):

A symbolic differentiation functional that handles expressions containing free and bound variables in an extended λ-calculus programming language is described. The differentiation primitive is implemented by augmenting the set of graph-reduction rules that define the evaluation of expressions. A formalization of partial derivatives of functions with regards to position of parameters is presented.

A comparison is made to other methods of automatic differentiation.

“FRACTRAN: A Simple Universal Programming Language for Arithmetic”, Conway 1987

1987-conway.pdf: “FRACTRAN: A Simple Universal Programming Language for Arithmetic”⁠, John H. Conway (1987-01-01):

To play the fraction game corresponding to a given list

f₁, f₂, …, f_k

of fractions and starting integer N, you repeatedly multiply the integer you have at any stage (initially N) by the earliest f_i in the list for which the answer is integral. Whenever there is no such f_i, the game stops.

“The Symbolics Ivory Processor: A 40 Bit Tagged Architecture Lisp Microprocessor”, Baker et al 1987

1987-baker.pdf: “The Symbolics Ivory Processor: A 40 Bit Tagged Architecture Lisp Microprocessor”⁠, Clark Baker, David Chan, Jim Cherry, Alan Corry, Greg Efland, Bruce Edwards, Mark Matson, Henry Minsky, et al (1987-01-01)

“Embedded Menus: Selecting Items in Context”, Koved & Shneiderman 1986

1986-koved.pdf: “Embedded menus: selecting items in context”⁠, Larry Koved, Ben Shneiderman (1986-04-01; design):

In many situations, embedded menus represent an attractive alternative to the more traditional explicit menus, particularly in touchtext, spelling checkers, language-based program editors, and graphics-based systems.

“Human Window on the World”, Michie 1985

1985-michie.pdf: “Human Window on the World”⁠, Donald Michie (1985-01-01; ai; backlinks)

“Surely You're Joking, Mr. Feynman! Chapter 18: Safecracker Meets Safecracker”, Feynman 1985

1985-feynman-surelyyourejokingmrfeynman-ch18-safecrackermeetsafecracker.pdf: “Surely You're Joking, Mr. Feynman! Chapter 18: Safecracker Meets Safecracker”⁠, Richard Feynman (1985; backlinks):

[In this chapter, Feynman discusses his fascination with locks and safes, and the ways he learns to crack different locks and safes. He also talks about the locks and safes there were at Los Alamos (the ones that held the secrets of the atomic bomb). Generally speaking, the safes containing this material, which is (understandably) considered top secret, are startlingly easy to crack. When Feynman and his colleagues first arrive at Los Alamos, the construction of the facility is not even complete yet, and there is almost no security at all for the “top secret” information. Even later, when the information is stored in safes and locked file cabinets, the locks are generally cheap, and it is easy for Feynman to determine what the combination is, as combinations were often reused. He can memorize common passwords, or watch people dialing carelessly to deduce several digits, and then brute-force the rest; often, people do not even change the factory default.]

“Randomness Conservation Inequalities; Information and Independence in Mathematical Theories”, Levin 1984

“Randomness conservation inequalities; information and independence in mathematical theories”⁠, Leonid A. Levin (1984-04; ai):

The article further develops Kolmogorov’s algorithmic complexity theory⁠.

The definition of randomness is modified to satisfy strong invariance properties (conservation inequalities). This allows definitions of concepts such as mutual information in individual infinite sequences.

Applications to several areas, like probability theory, theory of algorithms, intuitionistic logic are considered. These theories are simplified substantially with the postulate that the objects they consider are independent of (have small mutual information with) any sequence specified by a mathematical property.

“The Determination of the Value of Rado's Noncomputable Function Σ(𝑘) for Four-state Turing Machines”, Brady 1983

1983-brady.pdf: “The determination of the value of Rado's noncomputable function Σ(𝑘) for four-state Turing machines”⁠, Allen H. Brady (1983-04-01):

The well-defined but noncomputable functions Σ(k) and S(k) given by T. Rado as the “score” and “shift number” for the k-state Turing machine “Busy Beaver Game” were previously known only for k ≤ 3. The largest known lower bounds yielding the relations Σ(4) ≥ 13 and S(4) ≥ 107, reported by this author, supported the conjecture that these lower bounds are the actual particular values of the functions for k = 4.

The four-state case has previously been reduced to solving the blank input tape halting problem of only 5,820 individual machines. In this final stage of the k = 4 case, one appears to move into a heuristic level of higher order where it is necessary to treat each machine as representing a distinct theorem.

The remaining set consists of two primary classes in which a machine and its tape are viewed as the representation of a growing string of cellular automata. The proof techniques, embodied in programs, are entirely heuristic, while the inductive proofs, once established by the computer, are completely rigorous and become the key to the proof of the new and original mathematical results: Σ(4) = 13 and S(4) = 107.

“Epigrams on Programming”, Perlis 1982

1982-perlis.pdf: “Epigrams on Programming”⁠, Alan J. Perlis (1982-09-01; ai /​ ​gpt⁠, design⁠, humor⁠, philosophy⁠, spaced-repetition; backlinks):

[130 epigrams on computer science and technology, published in 1982, for ACM’s SIGPLAN journal, by noted computer scientist and programming language researcher Alan Perlis⁠. The epigrams are a series of short, programming-language-neutral, humorous statements about computers and programming, distilling lessons he had learned over his career, which are widely quoted.]

8. A programming language is low level when its programs require attention to the irrelevant….19. A language that doesn’t affect the way you think about programming, is not worth knowing….54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.

15. Everything should be built top-down, except the first time….30. In programming, everything we do is a special case of something more general—and often we know it too quickly….31. Simplicity does not precede complexity, but follows it….58. Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it….65. Make no mistake about it: Computers process numbers—not symbols. We measure our understanding (and control) by the extent to which we can arithmetize an activity….56. Software is under a constant tension. Being symbolic it is arbitrarily perfectible; but also it is arbitrarily changeable.

1. One man’s constant is another man’s variable. 34. The string is a stark data structure and everywhere it is passed there is much duplication of process. It is a perfect vehicle for hiding information.

36. The use of a program to prove the 4-color theorem will not change mathematics—it merely demonstrates that the theorem, a challenge for a century, is probably not important to mathematics.

39. Re graphics: A picture is worth 10K words—but only those to describe the picture. Hardly any sets of 10K words can be adequately described with pictures.

48. The best book on programming for the layman is Alice in Wonderland; but that’s because it’s the best book on anything for the layman.

77. The cybernetic exchange between man, computer and algorithm is like a game of musical chairs: The frantic search for balance always leaves one of the 3 standing ill at ease….79. A year spent in artificial intelligence is enough to make one believe in God….84. Motto for a research laboratory: What we work on today, others will first think of tomorrow.

91. The computer reminds one of Lon Chaney—it is the machine of a thousand faces.

7. It is easier to write an incorrect program than understand a correct one….93. When someone says “I want a programming language in which I need only say what I wish done”, give him a lollipop….102. One can’t proceed from the informal to the formal by formal means.

100. We will never run out of things to program as long as there is a single program around.

108. Whenever 2 programmers meet to criticize their programs, both are silent….112. Computer Science is embarrassed by the computer….115. Most people find the concept of programming obvious, but the doing impossible. 116. You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program. 117. It goes against the grain of modern education to teach children to program. What fun is there in making plans, acquiring discipline in organizing thoughts, devoting attention to detail and learning to be self-critical?

“On Holy Wars and a Plea for Peace”, Cohen 1981

1981-cohen.pdf: “On Holy Wars and a Plea for Peace”⁠, Daniel Cohen (1981-10-01; ai /​ ​gpt⁠, technology; backlinks):

Which bit should travel first? The bit from the big end or the bit from the little end? Can a war between Big Endians and Little Endians be avoided?

This article was written in an attempt to stop a war. I hope it is not too late for peace to prevail again. Many believe that the central question of this war is, What is the proper byte order in messages? More specifically, the question is, Which bit should travel first-the bit from the little end of the word or the bit from the big end of the word? Followers of the former approach are called Little Endians, or Lilliputians; followers of the latter are called Big Endians, or Blefuscuians. I employ these Swiftian terms because this modern conflict is so reminiscent of the holy war described in Gulliver’s Travels.

…To sum it all up, there are two camps, each with its own language. These languages are as compatible with each other as any Semitic and Latin languages. All Big Endians can talk only to each other. So can all the Little Endians, although there are some differences among the dialects used by different tribes. There is no middle ground—only one end can go first. As in all the religious wars of the past, power—not logic—will be the decisive factor. This is not the first holy war, and will probably not be the last. The “Reasonable, do it my way” approach does not work. Neither does the Esperanto approach of switching to yet another new language. Lest our communications world split along theses lines, we should take note of a certain book (not mentioned in the references), which has an interesting story about a similar phenomenon: the Tower of Babel. Lilliput and Blefuscu will never come to terms of their own free will. We need some Gulliver between the two islands to force a unified communication regime on all of us.

Of course, I hope that my way will be chosen, but it is not really critical. Agreement upon an order is more important than the order agreed upon.

Shall we toss a coin?

“A Correct Preprocessing Algorithm for Boyer-Moore String-Searching”, Rytter 1980

1980-rytter.pdf: “A Correct Preprocessing Algorithm for Boyer-Moore String-Searching”⁠, Wojciech Rytter (1980-01-01):

We present the correction to Knuth’s algorithm² for computing the table of pattern shifts later used in the Boyer-Moore algorithm for pattern matching.

“Alpha-particle-induced Soft Errors in Dynamic Memories”, May & Woods 1979

1979-may.pdf: “Alpha-particle-induced soft errors in dynamic memories”⁠, Timothy C. May, M. H. Woods (1979-01-01):

A new physical soft error mechanism in dynamic RAM’s and CCD’s is the upset of stored data by the passage of alpha particles through the memory array area. The alpha particles are emitted by the radioactive decay of uranium and thorium which are present in parts-per-million levels in packaging materials. When an alpha particle penetrates the die surface, it can create enough electron-hole pairs near a storage node to cause a random, single-bit error. Results of experiments and measurements of alpha activity of materials are reported and a physical model for the soft error is developed. Implications for the future of dynamic memories are also discussed.

“A Convergent Gambling Estimate Of The Entropy Of English”, Cover & King 1978

1978-cover.pdf: “A Convergent Gambling Estimate Of The Entropy Of English”⁠, Thomas M. Cover, Roger C. King (1978-07-01; psychology; backlinks):

In his original paper on the subject, Shannon found upper and lower bounds for the entropy of printed English based on the number of trials required for a subject to guess subsequent symbols in a given text. The guessing approach precludes asymptotic consistency of either the upper or lower bounds except for degenerate ergodic processes.

Shannon’s technique of guessing the next symbol is altered by having the subject place sequential bets on the next symbol of text. If S_n denotes the subject’s capital after n bets at 27 for 1 odds, and if it is assumed that the subject knows the underlying probability distribution for the process X, then the entropy estimate is Ĥ_n(X) = (1 − (1⁄n) log₂₇ S_n) log₂ 27 bits/​​symbol. If the subject does not know the true probability distribution for the stochastic process, then Ĥ_n(X) is an asymptotic upper bound for the true entropy. If X is stationary, EĤ_n(X) → H(X), H(X) being the true entropy of the process. Moreover, if X is ergodic, then by the Shannon-McMillan-Breiman theorem Ĥ_n(X) → H(X) with probability one.

Preliminary indications are that English text has an entropy of approximately 1.3 bits/​​symbol, which agrees well with Shannon’s estimate.

“Universal Sequential Search Problems”, Levin 1973

1973-levin.pdf: “Universal Sequential Search Problems”⁠, L. A. Levin (1973; ai):

[on Levin’s universal search⁠; for English discussion, see Levin 1984] Several well-known large-scale problems of the “sequential search” type are discussed, and it is proved that those problems can be solved only in the time that it takes to solve any problems of the indicated type, in general.

“The Humble Programmer [EWD340]”, Dijkstra 1972

“The Humble Programmer [EWD340]”⁠, Edsger W. Dijkstra (1972; math; backlinks):

[ACM Turing Lecture 1972 by famously opinionated mathematician Edsger W. Dijkstra]

…I had to make up my mind, either to stop programming and become a real, respectable theoretical physicist, or to carry my study of physics to a formal completion only, with a minimum of effort, and to become…, yes what? A programmer? But was that a respectable profession? For after all, what was programming? Where was the sound body of knowledge that could support it as an intellectually respectable discipline? I remember quite vividly how I envied my hardware colleagues, who, when asked about their professional competence, could at least point out that they knew everything about vacuum tubes, amplifiers and the rest, whereas I felt that, when faced with that question, I would stand empty-handed. Full of misgivings I knocked on van Wijngaarden’s office door, asking him whether I could “speak to him for a moment”; when I left his office a number of hours later, I was another person. For after having listened to my problems patiently, he agreed that up till that moment there was not much of a programming discipline, but then he went on to explain quietly that automatic computers were here to stay, that we were just at the beginning and could not I be one of the persons called to make programming a respectable discipline in the years to come? This was a turning point in my life and I completed my study of physics formally as quickly as I could.

…To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming had become an equally gigantic problem. In this sense the electronic industry has not solved a single problem, it has only created them, it has created the problem of using its products. To put it in another way: as the power of available machines grew by a factor of more than a thousand, society’s ambition to apply these machines grew in proportion, and it was the poor programmer who found his job in this exploded field of tension between ends and means. The increased power of the hardware, together with the perhaps even more dramatic increase in its reliability, made solutions feasible that the programmer had not dared to dream about a few years before.

…Automatic computers have now been with us for a quarter of a century. They have had a great impact on our society in their capacity of tools, but in that capacity their influence will be but a ripple on the surface of our culture, compared with the much more profound influence they will have in their capacity of intellectual challenge without precedent in the cultural history of mankind.

“On the Design of Display Processors”, Meyer & Sutherland 1968

“On the Design of Display Processors”⁠, T. H. Meyer, I. E. Sutherland (1968-06; backlinks):

The flexibility and power needed in the channel for a computer display are considered. To work efficiently, such a channel must have a sufficient number of instruction that it is best understood as a small processor rather than a powerful channel. As it was found that successive improvements to the display processor design lie on a circular path, by making improvements one can return to the original simple design plus one new general purpose computer for each trip around. The degree of physical separation between display and parent computer is a key factor in display processor design.

[Keywords: display processor design, display system, computer graphics, graphic terminal, displays, graphics, display generator, display channel, display programming, graphical interaction, remote displays, Wheel of Reincarnation]

“FLODAC - A Pure Fluid Digital Computer”, Gluskin et al 1964

1964-gluskin.pdf: “FLODAC - A Pure Fluid Digital Computer”⁠, R. S. Gluskin, M. Jacoby, T. D. Reader (1964-10-27)

“A Simple Randomization Procedure”, Sandelius 1962

1962-sandelius.pdf: “A Simple Randomization Procedure”⁠, Martin Sandelius (1962-07-01):

The paper describes a randomization procedure consisting in distributing a deck of cards into 10 decks using random decimal digits and repeating this step with each deck consisting of three or more cards. One random digit is used for randomizing a deck of two cards. This procedure, which is essentially a particular case of a general procedure described by Rao 1961⁠, is called the “multistage randomization procedure”, or MRP. Some applications are described. A recursive formula is given for the expected number of random digits required by MRP for the randomization of n symbols. A measure of the efficiency of a randomization procedure is presented. The efficiency of MRP is compared with the efficiencies of two other randomization procedures, and it is proved that MRP has an asymptotic efficiency of 100%.

“On Non-Computable Functions”, Rado 1962

1962-rado.pdf: “On Non-Computable Functions”⁠, T. Rado (1962-05-01):

[On the Busy Beaver function⁠.] The construction of non-computable functions used in this paper is based on the principle that a finite, non-empty set of non-negative integers has a largest element. Also, this principle is used only for sets which are exceptionally well-defined by current standards. No enumeration of computable functions is used, and in this sense the diagonal process is not employed. Thus, it appears that an apparently self-evident principle, of constant use in every area of mathematics, yields non-constructive entities.

“Generation of Random Permutations of Given Number of Elements Using Random Sampling Numbers”, Rao 1961

1961-rao.pdf: “Generation of Random Permutations of Given Number of Elements Using Random Sampling Numbers”⁠, C. Radhakrishna Rao (1961-08-01):

A general method is given for generating random permutations of integers using a table of random sampling numbers and without wasting the random numbers read. This is more convenient in practice, specially when random permutations of large numbers of elements are needed. It is suggested that even for permutations of small numbers, the method offers greater scope than consulting a table of a limited number of random permutations. [See also Sandelius 1962⁠, hence the description of this as “Rao-Sandelius shuffling”.]

“Coding Theorems for a Discrete Source With a Fidelity Criterion”, Shannon 1959

1959-shannon.pdf: “Coding Theorems for a Discrete Source With a Fidelity Criterion”⁠, Claude Shannon (1959; ai; backlinks):

Consider a discrete source producing a sequence of message letters from a finite alphabet. A single-letter distortion measure is given by an non-negative matrix (d_ij). The entry d_ij measures the “cost” or “distortion” if letter i is reproduced at the receiver as letter j. The average distortion of a communications system (source-coder-noisy channel-decoder) is taken to be $d={\sum }_{i,j}{P}_{ij}{d}_{ij}$ where P_ij is the probability of i being reproduced as j. It is shown that there is a function R(d) that measures the “equivalent rate” of the source for a given level of distortion. For coding purposes where a level d of distortion can be tolerated, the source acts like one within information rate R(d). Methods are given for calculating R(d), and various properties discussed. Finally, generalizations to ergodic sources, to continuous sources, and to distortion measures involving blocks of letters are developed.

“Correspondences Regarding Cryptography between John Nash and the NSA”, Nash 1955

1955-nash-nsacryptography.pdf: “Correspondences Regarding Cryptography between John Nash and the NSA”⁠, John Nash (1955-01; backlinks):

[In 1955, well-known mathematician John Nash was in correspondence with the United States National Security Agency. In these letters, Nash proposes a novel enciphering scheme. He also sets forth an important cryptographic principle that now underpin modern computational complexity theory and cryptography. In particular, he proposes a natural definition for “[security] in a practical sense”—that exponential computational effort is required for an enemy to recovery a secret key. Nash further conjectures that this property holds for any suitable enciphering mechanism.

These correspondences, recently declassified by the NSA¹; this document is the NSA scan with original images and drawings of Nash’s handwritten letters.]

“Ftfy: Fixes Text for You”, ftfy 2022

“ftfy: fixes text for you”⁠, ftfy (; ai /​ ​gpt⁠,  /​ ​poetry; backlinks):

ftfy fixes Unicode that’s broken in various ways.

The goal of ftfy is to take in bad Unicode and output good Unicode, for use in your Unicode-aware code. This is different from taking in non-Unicode and outputting Unicode, which is not a goal of ftfy. It also isn’t designed to protect you from having to write Unicode-aware code. ftfy helps those who help themselves.

Of course you’re better off if your input is decoded properly and has no glitches. But you often don’t have any control over your input; it’s someone else’s mistake, but it’s your problem now.

ftfy will do everything it can to fix the problem.

“ByteByteJump”, Wiki 2022

“ByteByteJump”⁠, Esolang Wiki (; backlinks):

ByteByteJump is an extremely simple One Instruction Set Computer (OISC). Its single instruction copies 1 byte from a memory location to another, and then performs an unconditional jump.

An instruction consists of 3 addresses stored consecutively in memory:

A, B, C

A is the source address, B is the destination address, and C is the jump address. N.B: ByteByteJump uses byte addressing⁠.

ByteByteJump has no ALU, but arithmetic operations and conditional jumps can still be performed by using self-modifying code and lookup tables (see Example). Despite its apparent simplicity, ByteByteJump actually belongs to the computational class of real microprocessors: the Linear bounded automaton⁠.

WordWordJump is the larger family of machines to which ByteByteJump belongs. An X×Y-bit WordWordJump machine has Y-bit data words and X×Y-bit address words, where X must be ≥2 for the machine to be able to compute. The optimal value for X (as explained here) seems to be 3.

ByteByte  /​ ​ ​ ​Jump is ByteByteJump’s sister machine. It splits the single instruction of ByteByteJump into two for improved code density.

Quine (computing)

Wikipedia

Linear programming

Wikipedia