{"id":401,"date":"2010-09-26T20:58:13","date_gmt":"2010-09-27T04:58:13","guid":{"rendered":"http:\/\/www.pagetable.com\/?p=401"},"modified":"2010-09-26T20:58:13","modified_gmt":"2010-09-27T04:58:13","slug":"measuring-the-entropy-of-the-mos-6502-cpu","status":"publish","type":"post","link":"https:\/\/www.pagetable.com\/?p=401","title":{"rendered":"Measuring the Entropy of the MOS 6502 CPU"},"content":{"rendered":"

Everything can be expressed in bits. It takes 4 kilobits to decompress ZIP data<\/a>, 25 kilobits to kill a human<\/a>, 43 megabits for a working Mac OS X kernel<\/a>, and 10^120 bits to describe our universe<\/a>. What is the entropy\/complexity of the 6502 CPU, you might wonder?<\/p>\n

You have probably already seen Visual 6502<\/a>, a simulator of the 6502 that operates at the transistor level and visualizes what’s going on inside the CPU. The data the program operates on was derived by converting a high-resolution photograph of the 6502 die into polygons, and converting these polygons into the node and transistor configuration.<\/p>\n

If you ignore the polygon data, which is only needed for visualization, the data to fully describe the 6502 consists of a set of nodes and a set of transistors.<\/p>\n

There are 1725 nodes in the 6502, and 3510 transistors. Every transistor has one node as an input that turns the transistor on or off. If the transistor is on, it connects two other nodes, and if it is off, it separates them. Every node can either be neutral, or be a pullup – the latter means that the node will behave as if it was connected to VCC whenever the path through this node is otherwise floating, i.e. not connected to VCC or GND (or an external pulldown).<\/p>\n

So the raw information that describes the 6502 is a set of nodes, for which there is one bit of information, whether it is a pullup node or a neutral node, as well as a set of transistors, which is a three-tuple consisting of gate, c1 and c2.<\/p>\n

The file segdefs.js<\/a> in visual6502 contains (next to the polygon information) the node state: “+” means pullup, “-” (or a missing node description) means neutral. The file transdefs.js<\/a> contains the transistor tuples.<\/p>\n

Stripped from irrelevant data, the 6502 description would look like this: The node states:<\/p>\n

\nBOOL nodes[] = {\n    \/*  0 *\/ 1,\n    \/*  1 *\/ 0,\n    \/*  2 *\/ 0,\n    \/*  3 *\/ 1,\n    \/*  4 *\/ 1,\n    \/*  5 *\/ 1,\n    \/*  6 *\/ 1,\n    \/*  7 *\/ 0,\n    \/*  8 *\/ 1,\n    \/*  9 *\/ 0,\n    \/* 10 *\/ 1,\n    [...]\n}\n<\/pre>\n
…and the transistors:<\/p>\n
\nstruct {\n\tint gate;\n\tint c1;\n\tint c2;\n} transistors[] = {\n    {357, 558, 217},\n    {1608, 657, 349},\n    {412, 558, 1146},\n    {558, 558, 943},\n    {826, 230, 657},\n    [...]\n}\n<\/pre>\n
A quick estimate would be 1 bit per node (pullup or neutral), and 3 times 11 bits (3 node numbers from 1 to 1725) per transistor, resulting in about 117 kilobits; but there is still a lot of redundancy in this representation.<\/p>\n
The transistor tuples can be represented in a much more compact way. First, there is no ordering for the transistors, so if we sort them by gate, we can encode just the difference between the current gate and the previous gate:<\/p>\n
\nstruct {\n\tint gate;\n\tint c1;\n\tint c2;\n} transistors[] = {\n    {1, 890, 558},\n    {4, 558, 11},\n    {5, 558, 146},\n    {6, 558, 282},\n    {6, 874, 657},\n    {7, 657, 1591},\n    {7, 657, 1591},\n    {7, 657, 1591},\n    {8, 150, 558},\n    [...]\n}\n<\/pre>\n
In practice, the difference between two gate nodes in the transistor list is a number between 0 and 4, so we could use 3 bits (instead of 11) for the gate. But in fact, it is enough to store a single bit: The nodes have no order either, so we can renumber them so that all nodes that are connected to a gate of a transistor are numbered from 0, and all nodes that are not connected to gates will be numbered above the ones with gates:<\/p>\n
\nstruct {\n\tint gate;\n\tint c1;\n\tint c2;\n} transistors[] = {\n    {0, 890, 558},\n    {1, 558, 11},\n    {2, 558, 146},\n    {3, 558, 282},\n    {3, 874, 657},\n    {4, 657, 1591},\n    {4, 657, 1591},\n    {4, 657, 1591},\n    {5, 150, 558},\n    [...]\n}\n<\/pre>\n
This way, there are no holes in the list of gates – a new transistor has either the next node number as its gate, or the same one again (i.e. a node is gate of several transistors). It is enough to store a single bit for the gate.<\/p>\n
The example above already shows that the nodes 657 and 558 show up a lot: These are VCC and GND, respectively. In fact, 234 transistors connect to VCC, and 2493 connect to GND. We could Huffman-encode the c1 and c2 nodes, but in practice, all other nodes except these two are relatively uniformly distributed, so let’s just special case them.<\/p>\n
There is also no ordering between the two nodes the transistor connects, and no transistor will ever connect VCC\/GND to VCC\/GND, so we only need to do the special VCC\/GND encoding for c1, and leave c2 as it is. Let’s use a single “1” bit to represent GND, “01” as VCC, and all other 11 bit node numbers will be prefixed with “00”, making them occupy 13 bits.<\/p>\n
This way, the 3510 values of c1 can be described in 2493 * 1 (the GNDs) + 234 * 2 (the VCCs) + 783 * (2 + 11) (the others) bits = 13140 bits. The c2 values occupy 3510 * 11 bits = 38610 bits. If you add the bit per transistor for the gate (i.e. 3510 bits), we’re at 55260 bits for the transistor description.<\/p>\n
Using arithmetic coding, we can describe a node number in about 10.75 bits instead of 11. This way, we save (783 + 3510) * 0.25 bits = 1073 bits. The transistor description thus fits into 54187 bits.<\/p>\n
As stated previously, we also need one bit per node for the pullup information. About half the nodes are pullup, and we don’t have the freedom of sorting and renaming the nodes any more (we’ve done that already for the transistor gates), so we’ll have to go with the 1725 raw bits.<\/p>\n
So the final number is 54187 bits + 1725 bits = 55912 bits. That’s 6989 bytes, or roughly 56 kilobits<\/b>, and about twice as big as H1N1<\/a>.<\/p>\n
With this number, we can estimate the complexity of a Commodore 64<\/a> to be about 200 kilobits (CPU, VIC, SID, 2xCIA, PLA) – plus another 160 kilobits of ROM.<\/p>\n
But wait: Did you see the duplicate transistors in the sorted list? Yes, there are some duplicates, in fact, there are only 3288 unique transistors. And when looking at it on a higher level, the 130 entry instruction decode ROM<\/a> has duplicates too: Only 115 are unique, leading to redundant paths in the node\/transistor graph. The reason for this redundancy is routing: There are only two dimensions in a computer chip (plus layers), so you cannot just connect anything to anything.<\/p>\n
The homework for today, dear reader, is to develop an algorithm that minimizes the description of the 6502 by removing duplicate transistors as well as equivalent paths.<\/p>\n","protected":false},"excerpt":{"rendered":"
Everything can be expressed in bits. It takes 4 kilobits to decompress ZIP data, 25 kilobits to kill a human, 43 megabits for a working Mac OS X kernel, and 10^120 bits to describe our universe. What is the entropy\/complexity of the 6502 CPU, you might wonder? You have probably already seen Visual 6502, a … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,5,26,33],"tags":[],"class_list":["post-401","post","type-post","status-publish","format-standard","hentry","category-2","category-archeology","category-puzzle","category-trivia"],"_links":{"self":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts\/401","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=401"}],"version-history":[{"count":0,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts\/401\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}