Takeaway: when performing an AllGather (or a ReduceScatter or AllReduce) in a throughput-bound regime, the actual communication time depends only on the size of the array and the available bandwidth, not the number of devices over which our array is sharded!

Note that this doesn’t depend on X! That’s kind of striking, because it means even though our TPUs are only locally connected, the locality of the connections doesn’t matter. We’re just bottlenecked by the speed of each link.

What is an AllGather? An AllGather is the first core MPI communication primitive we will discuss. An AllGather removes the sharding along an axis and reassembles the shards spread across devices onto each device along that axis. Using the notation above, an AllGather removes a subscript from a set of axes, e.g. AllGatherXY(A[IXY,J])→A[I,J] We don’t have to remove all subscripts for a given dimension, e.g. A[IXY,J]→A[IY,J] is also an AllGather, just over only a single axis. Also note that we may also wish to use an AllGather to remove non-contracting dimension sharding, for instance in the matrix multiply: A[IX,J]⋅B[J,K]→C[I,K] We could either AllGather A initially to remove the input sharding, or we can do the sharded matmul and then AllGather the result C. How is an AllGather actually performed? To perform a 1-dimensional AllGather around a single TPU axis (a ring), we basically have each TPU pass its shard around a ring until every device has a copy.A GPU AllGather can also work like this, where you create a ring out of the GPUs in a node and pass the chunks around in that (arbitrary) order. Here is an animation:

Takeaway: When multiplying matrices where one of the matrices is sharded along the contracting dimension, we generally AllGather it first so the contraction is no longer sharded, then do a local matmul.

A[I,JX]⋅B[J,K]→C[I,K] We cannot simply multiply the local chunks of A and B because we need to sum over the full contracting dimension of A, which is split across the X axis. Typically, we first “AllGather” the shards of A so every device has a full copy, and only then multiply against B:

Because neither A nor B has a sharded contracting dimension J, we can simply perform the local block matrix multiplies of the inputs and the results will already be sharded according to the desired output shardings. When both multiplicands have non-contracting dimensions sharded along the same axis, this is no longer true (see the invalid shardings section for details).

Lemma: when multiplying sharded matrices, the computation is valid and the output follows the sharding of the inputs unless the contracting dimension is sharded or both matrices are sharded along the same axis. For example, this works fine

Conveniently, we can boil down all possible shardings into roughly 4 cases we need to consider, each of which has a rule for what communication we need to add Case 1: neither input is sharded along the contracting dimension. We can multiply local shards without any communication. Case 2: one input has a sharded contracting dimension. We typically “AllGather” the sharded input along the contracting dimension. Case 3: both inputs are sharded along the contracting dimension. We can multiply the local shards, then “AllReduce” the result. Case 4: both inputs have a non-contracting dimension sharded along the same axis. We cannot proceed without AllGathering one of the two inputs first.

How do we describe this in code?

Each sharding will involve different communication

We illustrate the other possibilities in the figure below:

We can indicate that one of these dimensions has been partitioned across a mesh axis with a subscript mesh axis. For instance A[I_X, J] would mean that the I logical axis has been partitioned across the X mesh dimension, but that the J dimension is not partitioned, and the blocks remain partially-replicated across the Y mesh axis.

Sharding: A[I_X, J_Y], which tells us to shard the first axis, I, along the mesh axis X, and the second axis, J, along the mesh axis Y. This sharding tells us that each shard holds 1 / (\lvert X\rvert \cdot \lvert Y\rvert) of the array.

We use a variant of named-axis notation to describe how the tensor is sharded in blocks across the devices: we assume the existence of a 2D or 3D grid of devices called the device mesh where each axis has been given mesh axis names e.g. X, Y, and Z. We can then specify how the matrix data is laid out across the device mesh by describing how each named dimension of the array is partitioned across the physical mesh axes. We call this assignment a sharding.

Note how the sharded array still has the same global or logical shape as the unsharded array, say (4, 128), but it also has a device local shape, like (2, 64), which gives us the actual size in bytes that each TPU is holding (in the figure above, each TPU holds ¼ of the total array). Now we’ll generalize this to arbitrary arrays.

The VPU is the TPU’s vector arithmetic core. The VPU consists of a two dimensional SIMD vector machine (the VPU) that performs elementwise arithmetic operations like vadd (vector addition) or vmax (elementwise max) and a set of vector registers called VREGs that hold data for the VPU and MXU.

The scalar core is the control unit of the TPU. It fetches and dispatches all instructions and executes transfers from HBM into VMEM, and can be programmed to do scalar metadata work. Because the scalar core is single-threaded, one side-effect of this is that each core of the TPU is only capable of creating one DMA request per cycle. To put this in context, a single scalar core controls a VPU (consisting of 4096 ALUs), 4 MXUs, 2 XLUs, and multiple DMA engines. The highly skewed nature of control per unit compute is a source of hardware efficiency, but also limits the ability to do data dependent vectorization in any interesting way.

All lanes and sublanes execute the same program every cycle in a pure SIMD manner, but each ALU can perform a different operation. So we can e.g. process 1 vadd and 1 vsub in a single cycle, each of which operates on two full VREGs and writes the output to a third.

VPU: The VPU is a 2D vector arithmetic unit of shape (8, 128) where the 128 dimension is referred to as lane axis and the dimension of 8 is referred to as the sublane axis. Each (lane, sublane) pair on v5 contains 4 standard floating-point ALUs which are independent of each other. The VPU executes most arithmetic instructions in one cycle in each of its ALUs (like vadd or vector add) with a latency of 2 cycles, so e.g. in v5 you can add 4 pairs of f32 values together from VREGs in each cycle. A typical VPU instruction might look like {v2 = vadd.8x128.f32 v0, v1} where v0 and v1 are input VREGs and v2 is an output VREG.

VREGs: Each TPU v5p core has 64 32-bit VREGs (32 in TPU v4), giving us a total of about 64 * 8 * 128 * 4 = 256kB of VREG memory per core (or 2x this for the whole chip since we have two cores). A TPU v5p can load 3 registers from VMEM each cycle, and write 1 register to VMEM each cycle.

Key Takeaways TPUs are simple and can in most cases be thought of as a matrix multiply unit connected to memory (super fast), other chips over ICI (rather fast), and the rest of the datacenter over DCN (somewhat fast). Communication is limited by our various network bandwidths in order of speed: HBM bandwidth: Between a TensorCore and its associated HBM. ICI bandwidth: Between a TPU chip and its nearest 4 or 6 neighbors. PCIe bandwidth: Between a CPU host and its associated tray(s) of chips. DCN bandwidth: Between multiple CPU hosts, typically hosts not connected by ICI. Within a slice, TPUs are only connected to their nearest neighbors via ICI. This means communication over ICI between distant chips in a slice needs to hop over the intervening chips first. Weight matrices need to be padded to at least size 128 (256 on TPU v6e) in both dimensions to fill up the MXU (in fact, smaller axes are padded to 128). Lower precision matrix multiplication tends to be faster. TPUs can do int8 or int4 OPs roughly 2x/4x faster than bfloat16 FLOPs for generations that support it. VPU operations are still performed in fp32. To avoid bottlenecking the TPU compute unit, we need to make sure the amount of communication across each channel is proportional to its speed.

ICI is very fast relative to DCN, but is still slower than HBM bandwidth. For instance, a TPU v5p has: 2.8e12 bytes/s (2.8 TB/s) of HBM bandwidth per chip. 9e10 bytes/s (90 GB/s) of ICI bandwidth per axis, with 3 axes per chip.The page above lists 100 GB/s of bandwidth, which is slightly different from what's listed here. TPU ICI links have slightly different bandwidths depending on the operation being performed. You can generally use the numbers in this doc without worry. 6.25e9 bytes/s (6.25 GB/s) of DCN (egress) bandwidth per TPU (via 1-2 NICs on each host).

This nearest-neighbor connectivity is a key difference between TPUs and GPUs. GPUs are connected with a hierarchy of switches that approximate a point-to-point connection between every GPU, rather than using local connections like a TPU. Typically, GPUs within a node (8 GPUs for H100 or as many as 72 for B200 NVL72) are directly connected, while larger topologies require O(log(N)) hops between each GPU. On the one hand, that means GPUs can send arbitrary data within a small number of hops. On the other hand, TPUs are dramatically cheaper (since NVLink switches are expensive), simpler to wire together, and can scale to much larger topologies because the number of links per device and the bandwidth per device is constant. Read more here.

TPU pods (connected by ICI) can get really big: the maximum pod size (called a superpod) is 16x16x16 for TPU v4 and 16x20x28 for TPU v5p. These large pods are composed of reconfigurable cubes of 4x4x4 chips connected by optical wraparound linksThe optical switch is simply a reconfigurable connection with the same ICI bandwidth. It just lets us connect cubes while retaining a wraparound link. that we can reconfigure to connect very large topologies. Smaller topologies (e.g. 2x2x1, 2x2x2) can also be requested, albeit with no wraparounds. This is an important caveat, since it typically doubles the time of most communication. Any multiple of a full cube (e.g. 4x4x4 or 4x4x8) will have wraparounds provided by the optical switches.

The toroidal structure reduces the maximum distance between any two nodes from N to N / 2, making communication much faster. TPUs also have a “twisted torus” configuration that wraps the torus in a Mobius-strip like topology to further reduce the average distance between nodes.

PCIe bandwidth is limited: Like the HBM \leftrightarrow VMEM link, the CPU \leftrightarrow HBM PCIe connection has a specific bandwidth that limits how quickly you can load from host memory to HBM or vice-versa. PCIe bandwidth for TPU v4 is 16GB / second each way, for example, so close to 100x slower than HBM. We can load/offload data into the host (CPU) RAM, but not very quickly.

Chips are connected to each other through the ICI network in a Pod. In older generations (TPU v2 and TPU v3), inference chips (e.g., TPU v5e), and Trillium (TPU v6e), ICI (“inter-chip interconnects”) connects the 4 nearest neighbors (with edge links to form a 2D torus). TPU v4 and TPU v5p are connected to the nearest 6 neighbors (forming a 3D torus). Note these connections do not go through their hosts, they are direct links between chips.

Chips are arranged in sets of 4 on a ‘tray’ connected to a CPU host via PCIe network. This is the format most readers will be familiar with, 4 chips (8 cores, though usually treated as 4 logical megacores) exposed through Colab or a single TPU-VM. For inference chips like the TPU v5e, we have 2 trays per host, instead of 1, but also only 1 core per chip, giving us 8 chips = 8 cores.

Key takeaway: TPUs are very simple. They load weights from HBM into VMEM, then from VMEM into a systolic array which can perform around 200 trillion multiply-adds per second. The HBM \leftrightarrow VMEM and VMEM \leftrightarrow systolic array bandwidths set fundamental limits on what computations TPUs can do efficiently.

Generally, all TPU operations are pipelined and overlapped. To perform a matmul X \cdot A \to Y, a TPU would first need to copy chunks of matrices A and X from HBM into VMEM, then load them into the MXU which multiplies chunks of 8x128 (for X) and 128x128 (for A), then copy the result chunk by chunk back to HBM. To do this efficiently, the matmul is pipelined so the copies to/from VMEM are overlapped with the MXU work. This allows the MXU to continue working instead of waiting on memory transfers, keeping matmuls compute-bound, not memory-bound.

HBM (High Bandwidth Memory) is a big chunk of fast memory that stores tensors for use by the TensorCore. HBM usually has capacity on the order of tens of gigabytes (for example, TPU v5e has 16GiB of HBM). When needed for a computation, tensors are streamed out of HBM through VMEM (see below) into the MXU and the result is written from VMEM back to HBM. The bandwidth between HBM and the TensorCore (through VMEM) is known as “HBM bandwidth” (usually around 1-2TB/sec) and limits how fast computation can be done in memory-bound workloads.

The diagram above also includes a few other components like SMEM and the scalar unit, which are used for control flow handling and are discussed briefly in Appendix A, but aren’t crucial to understand. On the other hand, HBM is important and fairly simple:

VMEM (Vector Memory) is an on-chip scratchpad located in the TensorCore, close to the compute units. It is much smaller than HBM (for example, 128 MiB on TPU v5e) but has a much higher bandwidth to the MXU. VMEM operates somewhat like an L1/L2 cache on CPUs but is much larger and programmer-controlled. Data in HBM needs to be copied into VMEM before the TensorCore can do any computation with it.

he VPU (Vector Processing Unit) performs general mathematical operations like ReLU activations or pointwise addition or multiplication between vectors. Reductions (sums) are also performed here. Appendix A provides more details.

The MXU (Matrix Multiply Unit) is the core of the TensorCore. For most TPU generations, it performs one bf16[8,128] @ bf16[128,128] -> f32[8,128] matrix multiplyTPU v6e (Trillium) has a 256x256 MXU, while all previous generations use 128x128. every 8 cycles using a systolic array (see Appendix B for details). This is about 5e13 bf16 FLOPs/s per MXU at 1.5GHz on TPU v5e. Most TensorCores have 2 or 4 MXUs, so e.g. the total bf16 FLOPs/s for TPU v5e is 2e14. TPUs also support lower precision matmuls with higher throughput (e.g. each TPU v5e chip can do 4e14 int8 OPs/s).

Takeaway: for a bfloat16 matmul to be compute-bound on most TPUs, we need our per-replica token batch size to be greater than 240.Note that this is _not_ the batch size in the usual sense, where it means the batch size in sequences. It turns out most rooflines depend purely on the number of tokens, whether they belong to the same or different sequences. For instance if you have a batch size of 512 sequences of 4096 tokens on 2048 GPUs, you have a total batch size of `512 * 4096 = 2M` tokens, and a local batch size of 1k tokens.

replica) batch size B < 1024 tokens (not sequences) but D and F > 8000. Thus we generally become compute-bound when our per-replicaWe say per-replica because, if we do some kind of model sharding to increase the number of chips used in the matmul, we scale both our available compute and memory bandwidth by the same amount. Thus the critical batch size is true per independent copy of the model weights. batch size is greater than 240 tokens, a very simple rule!

We can get a nice simplification if we assume our “batch size”

hape \text{bf16}[B, D],

Example (dot product)

That means if an algorithm has a lower arithmetic intensity than 240 FLOPs/byte, it will be bound by byte loading and thus we won’t make good use of our hardware.This is only true if the algorithm loads its weights from HBM and runs in the MXU. As we'll discuss in the next section, we can sometimes store parameters in VMEM which has a much higher bandwidth. Many algorithms also run in the VPU, which has different performance characteristics. Let’s look at one such example:

The quantity \text{Intensity}(\text{Accelerator}) is the arithmetic intensity at which our accelerator achieves its peak FLOPs/s.

Definition: the arithmetic intensity of an algorithm is given by the ratio of the total FLOPs it performs to the number of bytes it needs to communicate — either within a chip or between chips.

we can lower-bound training and inference time by using the maximum of computation and communication time. We can also upper-bound with their sum

What is actually happening within the model that takes substantial time and how long should we expect it to take?

!count

events

fun (s, e) ->if s >= !cur_end then beginincr count;cur_end := eend

let count = ref 0 inlet cur_end = ref min_int

Array.sort (fun (_, e1) (_, e2) -> compare e1 e2) events

count := !count + 1

Write a function to compute the sum of the elements in an integer array.

[|1; 2; 3|].(2) <- 4

[|1; 2; 3|].(2)

[|[1; 2; 3]; [4; 5; 6]|]

[|[|1|]|]

[|true; false; true|]

Imagine that the for … = … to … do … done construct did not exist. How might we create the same behaviour?

What is the difference between [ref 5; ref 5] and let x = ref 5 in [x; x]?

What references have been created? What are their initial and final values after this expression has been evaluated? What is the type of this expression?

unit

Even if thecontestants are divided into teams, they compete as individuals

typedef long long ll

Around the mid-19th century, Swiss astronomer Rudolf Wolf rolled a pair of dice 20000 times, recording each outcome.

It's like the firing of the neurons is going only in one direction.

can’t train for in advance

weird learning disability

And we can bring common tasks into distribution quite easily through RL and SFT.

Blind/deaf people

frontier models are terabytes sized

Many billions of years of evolution is our pre-training

writing a dictionary of type (int × string) to a channel

Write a function which rotates a rect such that it is at least as tall as it is wide.

Rewrite the summary paragraph at the end of this chapter for the three argument function g a b c.

Why can we not write a function to halve all the elements of a list like this: map (( / ) 2) [10; 20; 30]? Write a suitable division function which can be partially applied in the manner we require.

member_all x ls

Write a function truncate which takes an integer and a list of lists, and returns a list of lists, each of which has been truncated to the given length. If a list is shorter than the given length, it is unchanged. Make use of partial application.

type of member x

What is its type?

Write the function union a b which forms the union of two dictionaries. The union of two dictionaries is the dictionary containing all the entries in one or other or both. In the case that a key is contained in both dictionaries, the value in the first should be preferred.

Write another function which uses the previous one, but handles the exception, and simply returns zero when a suitable integer cannot be found.

Write an exception definition and a function which calculates the largest integer smaller than or equal to the square root of a given integer. If the argument is negative, the exception should be raised.

Write another function smallest_or_zero which uses the smallest function but if Not_found is raised, returns zero.

exception.

Write the function for_all which, given a function of type α → bool and an argument list of type α list evaluates to true if and only if the function returns true for every element of the list. Give examples of its use.

Write a function filter which takes a function of type α → bool and an α list and returns a list of just those elements of the argument list for which the given function returns true.

Write a simple recursive function calm to replace exclamation marks in a char list with periods. For example calm [’H’; ’e’; ’l’; ’p’; ’!’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’!’] should evaluate to [’H’; ’e’; ’l’; ’p’; ’.’; ’ ’; ’F’; ’i’; ’r’; ’e’; ’.’]. Now rewrite your function to use map instead of recursion. What are the types of your functions?

We mentioned that the comparison functions like  <  work for many OCaml types. Can you determine, by experimentation, how they work for lists? For example, what is the result of [1; 2] < [2; 3]? What happens when we sort the following list of type char list list? Why?

We know that take and drop can fail if called with incorrect arguments. Show that this is never the case in msort.

Combine the sort and insert functions into a single sort function.

Write a function to detect if a list is already in sorted order.

Can you explain why the rev function we defined is inefficient? How does the time it takes to run relate to the size of its argument? Can you write a more efficient version using an accumulating argument? What is its efficiency in terms of time taken and space used?

Use your member function to write a function make_set which, given a list, returns a list which contains all the elements of the original list, but has no duplicate elements. For example, make_set [1; 2; 3; 3; 1] might return [2; 3; 1]. What is the type of your function?

Write a function evens which does the opposite to odds, returning the even numbered elements in a list. For example, evens [2; 4; 2; 4; 2] should return [4; 4]. What is the type of your function?

Write a function which, given a list, builds a palindrome from it. A palindrome is a list which equals its own reverse. You can assume the existence of rev and @. Write another function which determines if a list is a palindrome.

Write a function drop_last which returns all but the last element of a list. If the list is empty, it should return the empty list. So, for example, drop_last [1; 2; 4; 8] should return [1; 2; 4]. What about a tail recursive version?

Write a function count_true which counts the number of true elements in a list. For example, count_true [true; false; true] should return 2. What is the type of your function? Can you write a tail recursive version?

h is not used in the expression 1 + length t

There is a special pattern x..y to denote continuous ranges of characters, for example ’a’..’z’ will match all lowercase letters. Write functions islower and isupper, each of type char → bool, to decide on the case of a given letter.

What does match 1 + 1 with 2 -> match 2 + 2 with 3 -> 4 | 4 -> 5 evaluate to?

For each of the previous three questions, comment on whether you think it is easier to read the function with or without pattern matching. How might you expect this to change if the functions were much larger?

Rewrite the not function from the previous chapter in pattern matching style. Use pattern matching to write a recursive function which, given a positive integer n, returns the sum of all the integers from 1 to n. Use pattern matching to write a function which, given two numbers x and n, computes xn.

f a matches the pattern 1. If it does, just return 1. If not,

Can you suggest a way of preventing the non-termination of the factorial function in the case of a zero or negative argument?

Write a function power x n which raises x to the power n. Give its type.

Write a function isconsonant which, given a lower-case character in the range ’a’…’z’, determines if it is a consonant.

Write a recursive function which, given a number n, calculates the sum 1 + 2 + 3 + … + n. What is its type?

Write a function which returns true if both of its arguments are non-zero, and false otherwise. What is the type of your function?

Write a function which multiplies a given number by ten. What is its type?

# let rec gcd a b = if b = 0 then a else gcd b (a mod b);; val gcd : int -> int -> int = <fun> # gcd 64000 3456;; - : int = 128 Here is the evaluation:

what if we try to evaluate factorial (-1)?

What is the effect of the comparison operators like < and > on alphabetic values of type char? For example, what does ’p’ < ’q’ evaluate to? What is the effect of the comparison operators on the booleans, true and false?

Why not just use, for example, the integer 0 to represent false and the integer 1 for true? Why have a separate bool type at all?

Can you discover what the mod operator does when one or both of the operands are negative? What about if the first operand is zero? What if the second is zero?

What happens when you try to evaluate the expression 1 / 0? Why?

The range of numbers available is limited. There are two special numbers: min_int and max_int. What are their values on your computer? What happens when you evaluate the expressions max_int + 1 and min_int - 1?

A programmer writes 1+2 * 3+4. What does this evaluate to? What advice would you give him?

Consider the evaluations of the expressions 1 + 2 mod 3, (1 + 2) mod 3, and 1 + (2 mod 3). What can you conclude about the + and mod operators?

’%’

if true then false else true

true && false

true || false

1 <> 1

400 > 200

800 / 80 / 8

if and then (in our example 100 > 99) must have type bool

Sometimes, those students with least prior programming experience perform the best.

some countries persistently have lower defect rates than others on a timescale of decades1,

But once that company is past the VC-funded hyper growth phase and wants to maximize its profits, it will end up with a multi-thousand person platforms org, just like Google's, unless the company wants to leave hundreds of millions or billions of dollars a year on the table due to hardware and software inefficiency.

inimical

nd how much that would then change our de­ci­sions or ac­tions