Address Resolution Protocol for Application Specific Buffers

As part of the c10m problem, which advocates separating data plane from the control plane that routes the data, applications (such as ScyllaDB) have been built to bypass the kernel for data plane, opting to receive and transmit network packets directly from memory mapped buffers of a network card using a framework such as netmap or DPDK. But applications built this way hinges on exclusive control to the network interface. Running additional applications requires additional interfaces.

Previously, the kernel's network stack also acted as a dispatcher so that multiple programs can share one networking interface concurrently and only receive traffic destined for the specific program. On receiving the packet, the network card puts the packet into the next available RX buffer, hands it over to the kernel, and the kernel copies the data out after parsing the packet headers to determine how to route the data. Bypassing the kernel not only bypassed the data plane but also the control plane.

One solution is to let the kernel retain control of all RX buffers and handle the receive events. To dispatch the packet, the kernel would modify the application's address space to memory map the RX buffer for that packet. The problem with this approach is that first access of the mapping causes a soft page fault worth thousands of cycles, and unmapping causes costly TLB shoot-down. Rather than wasting that many cycles on the mapping, we might as well copy the data which can be done through a DMA controller.

If we want to avoid copying and the cost of mapping, then we need to perennially map RX buffers to the address space and somehow design the network interface to dispatch receiving packets to the right buffers. An application is identified by the IP address (layer 3) and port number (layer 4). The kernel traditionally handles the layer 3 and layer 4 semantics, but modifying the network card (layer 2) to understand higher layer is a violation of the abstraction imposed by the OSI model.

To keep a network card only aware of layer 2, each application will be assigned its own MAC address. The packets will only be directed to the RX buffers assigned to the packet's destination MAC address.

Traditionally, a MAC address can have one or more unique IP addresses, but one IP address uniquely maps to one MAC address. This means that each application will require its own IP address. For IPv6 this might not be a big problem, but for IPv4 this is salt on a wound caused by exhaustion of IP addresses which had already happened.

Address Resolution Protocol is used by a network gateway to translate destination IP address to destination MAC address as a packet enters a layer-2 Ethernet LAN from a layer-3 WAN domain. If we were to reuse an IP address across multiple MAC addresses, we need to modify ARP to resolve IP-port instead of just IP alone.

Under this architecture, the application-specific MAC addresses are assigned randomly with collision detection over broadcast. All programs on the same host will still share the same layer-3 address by differentiated by port number. The network gateway effectively handles the predisposition of packets into network interface RX buffers. The kernel retains the canonically assigned hardware MAC address for backwards compatibility. The kernel will still have its own RX buffers: they handle low-bandwidth network control traffic (ARP, ICMP, DHCP, etc.), packets destined to non-existent programs, as well as overflows when an application could not release its own RX buffers fast enough to receive more packets.

In summary, here are the architectural changes I'm proposing:

• Modify ARP to resolve IP-port to application specific MAC addresses.
• Each application on a host will have their own assigned RX buffers, identified by the application specific MAC address which is randomly assigned to not collide on the LAN.
• The RX buffers are perennially mapped into the application's address space.
• The kernel still handles the control plane, responding to ARP requests that maps IP-port to application specific MAC address.

This will realize an efficient zero-copy C10M solution with minimal modification to existing network architecture.

From Branch Prediction to Predictable Branching

Branch prediction is a technique in multi-stage pipelined CPU design to avoid pipeline stall. The reason of the stall is that early stages of the pipeline such as instruction fetch and decode cannot happen unless the CPU knows where to fetch the next instruction, but it has to wait for the result from earlier instructions to know which branch to take. Branch prediction speculatively executes one of the branch. If the prediction turns out to be good, the results of the execution is committed, otherwise the pipeline is flushed, and execution restarts from the actual branch.

There are two constructs in the program that cause branching. Conditional branches come from if-statements, where the code path takes the then-clause if the condition is true, or the else-clause otherwise. Indirect branches come from function pointers (used by callbacks), virtual method tables (used by object-oriented languages), and switch-statements. Unconditional direct branch does not need to be predicted.

Branch prediction has been well-studied, such as how various CPU microarchitectures implement branch prediction, and the limits of branch prediction. Since prediction misses are expensive, they measure the effectiveness of branch prediction by the percentage of hits. But I argue that branch prediction might not be the best approach to solve the pipeline stall problem. The better idea is to make branches predictable.

Predictable Indirect Branches

Let's say the program is about to call a virtual method of an object. The first word of the object is a pointer to the virtual table. The method pointer is the 7th word in the virtual table. The object pointer is stored in register %r0, and the stack pointer is in register %sp. For brevity, pointer arithmetic is expressed in the unit of a machine word.

; zeroth argument to the method is the object pointer.
store %r0 -> %sp + 0

; compute the arguments and store them.
...
store %r1 -> %sp + 1
...
store %r2 -> %sp + 2

; prepare to call the method.
load %r0 -> %r3      ; load address of the virtual table
load %r3 + 7 -> %r4  ; load address of the method
call %r4

The reason of the pipeline stall is because the call instruction doesn't know what is in %r4 until the instruction to load method address into %r4 is executed.

I included the code to compute the function call arguments to emphasize the fact that there is a lot of work that the CPU could be doing before the real branch target is computed. We can avoid the pipeline stall if we just reorder the work slightly.

; prepare to call the method.
load %r0 -> %r3      ; load address of the virtual table
load %r3 + 7 -> %r4  ; load address of the method
setcall %r4  ; set the branch target but do not branch yet.

; zeroth argument to the method is the object pointer.
store %r0 -> %sp + 0

; compute the arguments and store them.
...
store %r1 -> %sp + 1
...
store %r2 -> %sp + 2

call  ; do the actual call.

In this latter example, we compute the branch target first and do the other work later. By the time the pipeline needs to decode the next instruction after the branch, setcall should have been executed and provided us with the actual target. If not, it is okay for the pipeline to stall for a bit. Programs that do not use setcall/call can still benefit from the branch prediction buffer.

Predictable Conditional Branches

Conditional branches are a bit trickier because we can't generally precompute the condition. One technique used by the programmer is to compute both branches and mask the result of either one. The mask can be created using a bit manipulation technique. For example, the statement:

int result = condition? expression_true : expression_false;

Can be decomposed as:

int result_true = expression_true;
int result_false = expression_false;
int mask = to_mask(condition);
int result = (mask & result_true) | (~mask & result_false);

This approach only works if the expressions are trivial to compute. Otherwise the redundant work would be more expensive than pipeline stall.

A more general approach recognizes the fact that conditional branches are often asymmetric: one branch is the fast path in a tight loop, and the other branch is the slow path. Take for example an implementation of the strlen(s) function.

size_t strlen(const char *s) {
  size_t n = 0;
  while (*s)
    ++n, ++s;
  return n;
}

Its assembly pseudo-code might be:

strlen:
  load %sp -> %r1  ; load s into %r1
  xor %r0, %r0 -> %r0  ; zero %r0 as n

loop:
  loadbyte %r1 -> %r2  ; dereference *s
  bz %r2, endloop  ; branch if zero
  inc %r0
  inc %r1
  b loop  ; unconditional, no prediction needed.

endloop:
  r  ; return value in %r0

The basic block between loop and endloop is the tight loop. One way to argue that it must run as quickly as possible is because it runs many times; that's the classic branch prediction argument that sought to maximize the probability of prediction hits.

But we can also argue that branches should always favor the tight loop because the consequence of taking the bz branch result in more expensive code (function return), whereas the cost of not taking the branch is cheap. This is true even if s is an empty string. In other words, we are making the branch predictable by analyzing whether the cost of prediction miss can be amortized into the code that follows.

The consequence of misprediction can be visualized as the following table:

	Fast Path	Slow Path
Hit	For The Win!	Not a big win.
Miss	Huge penalty!	Small penalty.

There are two ways to distinguish fast and slow paths. The compiler can insert branch hints, which should work well because branch misprediction cost is static. The CPU can also decode ahead and compute the path cost of both branches. In the case where it is difficult to tell between the fast and slow paths, the CPU can always use the branch prediction heuristic based on historical data.

Conclusion

Here I presented methods to make branching predictable. For the indirect branch, the idea is to compute the branch target as early as we can before the actual branch, and there are usually more work that could be done in the mean time. For the conditional branch, the idea is to distinguish the fast and slow paths, and prefer to branch to the fast path because the slow path is penalized less by miss cost. Both methods can be used in addition to the branch prediction buffer based on historical data.

Bitrot Resistance on a Single Drive

This morning I read an interesting summary on Slashdot about bitrot under HFS+. The article is a bit misleading because bitrot is not really an HFS+ problem per se, but the author's qualm is that HFS+ does not support data integrity feature like ZFS. This merely echoes a sentiment that ZFS is slowly making its way to Mac OS X which was not happening due to the NetApp v. Sun Microsystems (now Oracle) patent lawsuit claiming that the copy-on-write feature in ZFS infringes on NetApp's WAFL technology. Although the lawsuit was dismissed in 2010, it appears that Apple had lost interest.

But is ZFS really the silver bullet against bitrot? My argument is that bitrot should not be handled at the filesystem layer, but done at the block storage layer, if you only put data on a single drive.

ZFS data integrity uses block checksumming. Rather than storing the checksum in the block, the block pointers are really a pair (address, checksum). This pointer structure is propagated all the way to the root, forming a Merkle tree. You can configure the filesystem to store several copies of a block, which divides the usable data capacity of a drive by the number of copies (or \( 1 / k \) of the capacity, where \( k \) is the number of copies).  ZFS can also manage a disk pool for you in a RAID-like configuration. RAID-Z uses parity so the drive capacity is \( (n - 1)/n \) where \( n \) is the number of drives (which must be identically sized). Most people don't have disk arrays, so they're stuck with multiple copies at \( 1 / k \) capacity.

Given that the original author of the bitrot article suffered only 23 files over a 6 year period (on the filesystem there are usually millions of files), reducing your drive capacity to a half or a third seems a dire price to pay.

The ideal case of bitrot resistance is if the block storage performs Reed-Solomon error correction. This have been the way CD-ROM stores data. CD-ROM physical sectors are 2352 bytes, but data sectors are 2048 bytes; the hidden bytes are used for error correction.

Note that Reed-Solomon is generally more robust the more data there are. For hard drives (magnetic spinning discs, not SSDs), it would make sense to do Reed-Solomon on a whole cylinder, since hard drive performance overhead is bottlenecked on seeking: movement of the reading heads to a particular cylinder position is a delicate operation. Reading the extra sectors in a cylinder is free. The drive doesn't have to implement this. The extra error correction can be done by the logical volume manager, which is a block storage layer underneath the filesystem but above the actual device.

But one complication is logical block addressing (LBA) that numbers sectors linearly in order to overcome disk size limited by BIOS int 13h, which is an outdated API for accessing disk drives in the MS-DOS days. LBA hides the disk geometry due to the linear numbering. The error-correcting logical block layer could be more efficient if it knows the underlying disk geometry. Otherwise the error correction might span cross two physical cylinders, which is suboptimal. But it might not be too big of a deal since moving the disk head to the next cylinder is much easier than swinging it across the disk surface. The notion of a cylinder is also largely decimated in modern disks because outer cylinders have bigger circumference, and can have more sectors than inner cylinders. It would suffice to pretend that a pseudo-cylinder be merely a span of continuous sectors.

To get the best performance, the filesystem might wish to use a logical block size equaling the cylinder size. Depending on the disk geometry, the block size would typically be ~1MB. This would waste space unless the filesystem can pack small files, like BtrFS. Therefore, it is possible to achieve bitrot resistance on a single drive without performance impact.

Now, if you want to put data across an array of drives, then doing Reed-Solomon error correction across all drives that might fail independently would be the ideal. Note that you don't want to do error correction across drives with correlated failure, e.g. (1) drives from the same manufacturing batch subject to the same wear, or (2) drives that can be destroyed by the same power failure or surge at a site.

Revamping signal system for the subway

The other day I was watching an old episode of Extreme Engineering, Subways of America. One of the problems with scheduling is collision avoidance. In order to reduce the likelihood of collision, you space out the trains or keep them moving slowly. But that means the utilization of the track becomes low or you increase commuter time. Collision is a huge problem for subway because visibility in the underground tunnel is low, and once an accident happens, there are only very limited escape options. A smoking fire can quickly turn into a disaster. The signal system allows collision avoidance in a more predictable way, so that efficiency can be improved.

Although the episode focused more on NYC subway, I take the MBTA every day to work, and I often wished its efficiency could be improved. The signal systems of the mass transit lines, red and blue, have been recently revamped (I don't take the orange line so I don't know). The green line, on the other hand, is still using an old system. They basically stick a signal light with a sensor and a timer to the right of the track. When a train passes, the sensor detects the train, and turns the signal light red. After 10 seconds, the signal light turns yellow, and another minute the signal light turns green. (I have not actually timed the intervals. I just pulled them out from memory). Signal lights are spaced every some distance. When you hear MBTA announce signaling problem, one of the light bulbs probably just burned out or the light got stuck in green.

What a signal system boils down to is a way to estimate distance between two trains, so the conductor can adjust the speed of the train accordingly. But installing signal systems can be expensive particularly if it requires new wiring along the tunnel. It requires taking parts of the tunnel offline, and servicing is expensive. The ingenuity of the timed signal lights is that it's a decentralized, cost-effective solution that worked well 100 years ago when the pace of life was slower.

I propose a similarly decentralized signal system where each train gains the visibility of its distance from other trains without the need to install new wiring to the tunnel. The key idea lies in applying Broadband over Power Lines technology which converts the "third rail" or the power line into an ether where communication can take place. Similar to how GPS and NTP systems work, trains will broadcast time-stamped messages at a given interval, and by measuring the round-trip time of these messages, trains can estimate the distances between each other. Stationary beacons can be placed at fixed distances on the track so trains can also track their absolute position.

The stationary beacon also detect if a train is passing without the active broadcasting working. If so, it sends a warning to all trains. The train immediately behind the warning beacon will ask the beacon how long ago the no-signal train has passed and adjusts its speed accordingly, essentially reverting back to the old system. The system is successful if it would allow both old and new trains to work on the same track. A graceful upgrade option is also a graceful downgrade option.

Now done with the logistics, here is the technical part. Light travels about 30cm each nanosecond. This is called a "light-foot." Electric signal travels at similar speed. We can convert the round-trip time to a distance, but we're constrained by the accuracy and precision we can measure time. Computer processors run at 1GHz or more, so for the sake of discussion we can equate 1 nanosecond to 1 CPU cycle. It is generally possible to use off-the-shelf computers for this purpose, except off-the-shelf operating systems are not to the task. We need a dedicated real-time operating system that can achieve latency in just a handful of CPU cycles. Since main memory access incurs cycle penalty of 20 cycles or more, the system will run entirely off the CPU's L2 cache.

Using a general programmable CPU has the benefit that we can easily design and test the time-distance measurement protocol to make it safer, more efficient, and more robust. On the other hand, if this is programmed in hardware, then it would take many years. GPS has its root from 1940's, with initial deployment in its current form in the 1990's. It took GPS more than 20 years to reach current maturity. Although we're not launching satellites, the positioning system proposed here requires faster response time and more precise distance measurement, and will likely not be doable in another 10 years in hardware. I think we can already develop the technology in software in a matter of a few years.

Eliminate Cache Coherence from HyperTransport

Processors are equipped with a cache to speed up memory access because main memory access speed failed to keep up with processor speed. On a symmetric multi-processor system, each processor possesses a private cache but all share a memory bus. Cache coherence protocol makes sure that all the private caches maintain a consistent copy of a portion of the main memory even though any processor may write to the main memory any time.

Things get complicated with NUMA where processors now come with their own memory controller and their local main memory. They still have their private cache. Processors no longer share a bus, but they send messages to one another through a point-to-point communication channel. A message may be routed through multiple hops in a network of processors. This is how HyperTransport works. Furthermore, a socket can actually house two multi-core dies, and on a quad socket system it can create quite an interesting topology.

In order to create the illusion of shared memory, a processor will need to talk to another processor for accessing remote main memory. The longer the hops between processors, the higher the latency. But HyperTransport 3.1 operates at 3.2GHz, so we're still talking about just 1 or 2 CPU cycles. Memory access time clocks in at 20 cycles or more.

Current generation AMD processor caches both local as well as remote main memory. Cache coherence over HyperTransport is a lot more complicated. If a processor wishes to conduct a transaction and invalidate the caches of other processors, it must send a message to all processors and wait until all of them to respond. This creates a torrent of messages over the HyperTransport link.

A recent feature called HT assist uses parts of the L3 cache to keep a record of which processors' caches need to be invalidated. This reduces the number of messages that need to be sent, increasing effective memory bandwidth.

Having said all this, here is my epiphany: what if we prohibit a processor from caching remote memory? It will only cache local memory, but will answer memory access on behalf of a remote processor from the cache. This would work well because accessing a remote cache over HyperTransport is still faster than accessing local memory. And we can do without the overheads of cache coherence protocol.

Furthermore, as more programs become NUMA aware, their structure would adapt so that they access primarily memory local to the processor, but leverage remote memory access as a mean of communication. Their performance will not be hindered by not caching remote memory, and it frees up the precious bandwidth on HyperTransport to do useful communication.

Pogoplug V4 spec for future reference

NAND partitions:

/ # cat /proc/mtd
dev:    size   erasesize  name
mtd0: 00200000 00020000 "u-boot"
mtd1: 00300000 00020000 "uImage"
mtd2: 00300000 00020000 "uImage2"
mtd3: 00800000 00020000 "failsafe"
mtd4: 07000000 00020000 "root"

PCI and USB devices:

/ # lspci
00:01.0 Class 0c03: 1b73:1009
/ # lsusb
Bus 001 Device 001: ID 1d6b:0002
Bus 002 Device 001: ID 1d6b:0002
Bus 001 Device 002: ID 0781:5571

CPU info:

/ # cat /proc/cpuinfo 
Processor       : Feroceon 88FR131 rev 1 (v5l)
BogoMIPS        : 799.53
Features        : swp half thumb fastmult edsp 
CPU implementer : 0x56
CPU architecture: 5TE
CPU variant     : 0x2
CPU part        : 0x131
CPU revision    : 1

Hardware        : Feroceon-KW
Revision        : 0000
Serial          : 0000000000000000

dmesg output:

~ # dmesg
console=ttyS0,115200 root=ubi0:rootfs ubi.mtd=4,2048 rootfstype=ubifs
<4>[    0.000000] PID hash table entries: 512 (order: 9, 2048 bytes)
<6>[    0.000000] Dentry cache hash table entries: 16384 (order: 4, 65536 bytes)
<6>[    0.000000] Inode-cache hash table entries: 8192 (order: 3, 32768 bytes)
<6>[    0.000000] Memory: 128MB = 128MB total
<5>[    0.000000] Memory: 118356KB available (3852K code, 261K data, 124K init, 0K highmem)
<6>[    0.000000] Hierarchical RCU implementation.
<6>[    0.000000] NR_IRQS:128
<4>[    0.000000] Console: colour dummy device 80x30
<6>[    0.000000] Calibrating delay loop... 799.53 BogoMIPS (lpj=3997696)
<4>[    0.230000] Mount-cache hash table entries: 512
<6>[    0.230000] CPU: Testing write buffer coherency: ok
<6>[    0.230000] NET: Registered protocol family 16
<6>[    0.230000] Feroceon L2: Enabling L2
<6>[    0.230000] Feroceon L2: Cache support initialised.
<4>[    0.230000] 
<4>[    0.230000] CPU Interface
<4>[    0.230000] -------------
<4>[    0.230000] SDRAM_CS0 ....base 00000000, size 128MB 
<4>[    0.230000] SDRAM_CS1 ....disable
<4>[    0.230000] SDRAM_CS2 ....disable
<4>[    0.230000] SDRAM_CS3 ....disable
<4>[    0.230000] PEX0_MEM ....base e0000000, size 128MB 
<4>[    0.230000] PEX0_IO ....base f2000000, size   1MB 
<4>[    0.230000] PEX1_MEM ....no such
<4>[    0.230000] PEX1_IO ....no such
<4>[    0.230000] INTER_REGS ....base f1000000, size   1MB 
<4>[    0.230000] NFLASH_CS ....base fa000000, size   2MB 
<4>[    0.230000] SPI_CS ....base f4000000, size  16MB 
<4>[    0.230000] BOOT_ROM_CS ....no such
<4>[    0.230000] DEV_BOOTCS ....no such
<4>[    0.230000] CRYPT_ENG ....base f0000000, size   2MB 
<4>[    0.230000] 
<4>[    0.230000]   Marvell Development Board (LSP Version KW_LSP_5.1.3_patch18)-- RD-88F6192A-NAS  Soc: 88F6192 A1 LE
<4>[    0.230000] 
<4>[    0.230000]  Detected Tclk 166666667 and SysClk 200000000 
<4>[    0.230000] Marvell USB EHCI Host controller #0: c403e740
<4>[    0.730000] PEX0 interface detected Link X1
<7>[    0.730000] pci 0000:00:01.0: reg 10 64bit mmio: [0x40000000-0x4000ffff]
<7>[    0.730000] pci 0000:00:01.0: reg 18 64bit mmio: [0x40010000-0x40010fff]
<7>[    0.730000] pci 0000:00:01.0: reg 20 64bit mmio: [0x40011000-0x40011fff]
<7>[    0.740000] pci 0000:00:01.0: supports D1
<6>[    0.740000] pci 0000:00:01.0: PME# supported from D0 D1 D3hot
<6>[    0.740000] pci 0000:00:01.0: PME# disabled
<6>[    0.740000] PCI: bus0: Fast back to back transfers disabled
<4>[    0.740000] mvPexLocalBusNumSet: ERR. Invalid PEX interface 1
<4>[    0.750000] bio: create slab <bio-0> at 0
<5>[    0.750000] SCSI subsystem initialized
<6>[    0.750000] usbcore: registered new interface driver usbfs
<6>[    0.750000] usbcore: registered new interface driver hub
<6>[    0.750000] usbcore: registered new device driver usb
<6>[    0.750000] NET: Registered protocol family 2
<6>[    0.750000] IP route cache hash table entries: 1024 (order: 0, 4096 bytes)
<6>[    0.750000] TCP established hash table entries: 4096 (order: 3, 32768 bytes)
<6>[    0.750000] TCP bind hash table entries: 4096 (order: 2, 16384 bytes)
<6>[    0.750000] TCP: Hash tables configured (established 4096 bind 4096)
<6>[    0.750000] TCP reno registered
<6>[    0.750000] NET: Registered protocol family 1
<6>[    0.750000] cpufreq: Init kirkwood cpufreq driver
<7>[    0.750000] cpufreq: High frequency: 800000KHz - Low frequency: 200000KHz
<7>[    0.750000] cpufreq: Setting CPU Frequency to 800000 KHz
<7>[    0.750000] cpufreq: Setting PowerSaveState to off
<6>[    0.760000] XOR registered 4 channels
<6>[    0.760000] XOR 2nd invalidate WA enabled
<4>[    0.760000] cesadev_init(c000d7fc)
<4>[    0.760000] mvCesaInit: sessions=640, queue=64, pSram=f0000000
<6>[    0.760000] squashfs: version 4.0 (2009/01/31) Phillip Lougher
<6>[    0.770000] msgmni has been set to 231
<6>[    0.770000] alg: No test for cipher_null (cipher_null-generic)
<6>[    0.770000] alg: No test for ecb(cipher_null) (ecb-cipher_null)
<6>[    0.770000] alg: No test for digest_null (digest_null-generic)
<6>[    0.770000] alg: No test for compress_null (compress_null-generic)
<6>[    0.780000] alg: No test for stdrng (krng)
<6>[    0.780000] alg: No test for hmac(digest_null) (hmac(digest_null-generic))
<6>[    0.790000] Block layer SCSI generic (bsg) driver version 0.4 loaded (major 253)
<6>[    0.790000] io scheduler noop registered
<6>[    0.790000] io scheduler anticipatory registered (default)
<4>[    0.790000] Initializing ths8200_init
<4>[    0.790000] Initializing dove_adi9889_init
<6>[    0.810000] Serial: 8250/16550 driver, 4 ports, IRQ sharing disabled
<6>[    0.810000] serial8250.0: ttyS0 at MMIO 0xf1012000 (irq = 33) is a 16550A
<6>[    0.810000] console [ttyS0] enabled
<4>[    0.820000] Integrated Sata device found
<4>[    0.830000] IRQ 21/mvSata: IRQF_DISABLED is not guaranteed on shared IRQs
<6>[    0.850000] scsi0 : Marvell SCSI to SATA adapter
<6>[    0.860000] scsi1 : Marvell SCSI to SATA adapter
<4>[    0.870000] Loading Marvell Ethernet Driver:
<4>[    0.870000]   o Cached descriptors in DRAM
<4>[    0.880000]   o DRAM SW cache-coherency
<4>[    0.880000]   o 1 Giga ports supported
<4>[    0.880000]   o Single RX Queue support - ETH_DEF_RXQ=0
<4>[    0.890000]   o Single TX Queue support - ETH_DEF_TXQ=0
<4>[    0.890000]   o TCP segmentation offload (TSO) supported
<4>[    0.900000]   o Large Receive offload (LRO) supported
<4>[    0.900000]   o Receive checksum offload supported
<4>[    0.910000]   o Transmit checksum offload supported
<4>[    0.910000]   o Network Fast Processing (Routing) supported - (Disabled)
<4>[    0.920000]   o Driver ERROR statistics enabled
<4>[    0.930000]   o Proc tool API enabled
<4>[    0.930000]   o SKB Reuse supported - (Disabled)
<4>[    0.930000]   o SKB Recycle supported - (Disabled)
<4>[    0.940000]   o Rx descripors: q0=128
<4>[    0.940000]   o Tx descripors: q0=532
<4>[    0.950000]   o Loading network interface(s):
<4>[    0.950000]      o register under mv88fx_eth platform
<4>[    0.960000]      o eth0, ifindex = 2, GbE port = 0
<4>[    0.960000] 
<4>[    0.960000] mvFpRuleDb (c45b2000): 1024 entries, 4096 bytes
<4>[    0.970000] Counter=0, opIdx=6, overhead=16
<4>[    0.970000] Counter=1, opIdx=2, overhead=0
<4>[    0.980000] Counter=2, opIdx=1, overhead=18
<4>[    0.980000] Counter=3, opIdx=2, overhead=0
<6>[    0.990000] tun: Universal TUN/TAP device driver, 1.6
<6>[    0.990000] tun: (C) 1999-2004 Max Krasnyansky <maxk@qualcomm.com>
<6>[    1.000000] NAND device: Manufacturer ID: 0xad, Chip ID: 0xf1 (Hynix NAND 128MiB 3,3V 8-bit)
<6>[    1.010000] Scanning device for bad blocks
<4>[    1.060000] Using static partition definition
<5>[    1.060000] Creating 5 MTD partitions on "nand_mtd":
<5>[    1.070000] 0x000000000000-0x000000200000 : "u-boot"
<5>[    1.070000] 0x000000200000-0x000000500000 : "uImage"
<5>[    1.080000] 0x000000500000-0x000000800000 : "uImage2"
<5>[    1.080000] 0x000000800000-0x000001000000 : "failsafe"
<5>[    1.090000] 0x000001000000-0x000008000000 : "root"
<5>[    1.100000] UBI: attaching mtd4 to ubi0
<5>[    1.100000] UBI: physical eraseblock size:   131072 bytes (128 KiB)
<5>[    1.110000] UBI: logical eraseblock size:    126976 bytes
<5>[    1.110000] UBI: smallest flash I/O unit:    2048
<5>[    1.120000] UBI: sub-page size:              512
<5>[    1.120000] UBI: VID header offset:          2048 (aligned 2048)
<5>[    1.130000] UBI: data offset:                4096
<5>[    1.350000] UBI: attached mtd4 to ubi0
<5>[    1.350000] UBI: MTD device name:            "root"
<5>[    1.360000] UBI: MTD device size:            112 MiB
<5>[    1.360000] UBI: number of good PEBs:        896
<5>[    1.370000] UBI: number of bad PEBs:         0
<5>[    1.370000] UBI: max. allowed volumes:       128
<5>[    1.380000] UBI: wear-leveling threshold:    4096
<5>[    1.380000] UBI: number of internal volumes: 1
<5>[    1.390000] UBI: number of user volumes:     1
<5>[    1.390000] UBI: available PEBs:             0
<5>[    1.400000] UBI: total number of reserved PEBs: 896
<5>[    1.400000] UBI: number of PEBs reserved for bad PEB handling: 8
<5>[    1.410000] UBI: max/mean erase counter: 1/0
<5>[    1.410000] UBI: image sequence number: 0
<6>[    1.420000] ehci_hcd: USB 2.0 'Enhanced' Host Controller (EHCI) Driver
<6>[    1.420000] ehci_marvell ehci_marvell.70059: Marvell Orion EHCI
<6>[    1.430000] ehci_marvell ehci_marvell.70059: new USB bus registered, assigned bus number 1
<5>[    1.440000] UBI: background thread "ubi_bgt0d" started, PID 452
<6>[    1.470000] ehci_marvell ehci_marvell.70059: irq 19, io base 0xf1050100
<6>[    1.490000] ehci_marvell ehci_marvell.70059: USB 2.0 started, EHCI 1.00
<6>[    1.490000] usb usb1: configuration #1 chosen from 1 choice
<6>[    1.500000] hub 1-0:1.0: USB hub found
<6>[    1.500000] hub 1-0:1.0: 1 port detected
<6>[    1.510000] xhci_hcd 0000:00:01.0: xHCI Host Controller
<6>[    1.510000] xhci_hcd 0000:00:01.0: new USB bus registered, assigned bus number 2
<6>[    1.520000] xhci_hcd 0000:00:01.0: irq 9, io mem 0xe0000000
<4>[    1.530000] usb usb2: config 1 interface 0 altsetting 0 endpoint 0x81 has no SuperSpeed companion descriptor
<6>[    1.540000] usb usb2: configuration #1 chosen from 1 choice
<7>[    1.540000] xHCI xhci_add_endpoint called for root hub
<7>[    1.540000] xHCI xhci_check_bandwidth called for root hub
<6>[    1.540000] hub 2-0:1.0: USB hub found
<6>[    1.550000] hub 2-0:1.0: 4 ports detected
<6>[    1.550000] Initializing USB Mass Storage driver...
<6>[    1.550000] usbcore: registered new interface driver usb-storage
<6>[    1.560000] USB Mass Storage support registered.
<6>[    1.570000] usbcore: registered new interface driver ums-datafab
<6>[    1.570000] usbcore: registered new interface driver ums-freecom
<6>[    1.580000] usbcore: registered new interface driver ums-jumpshot
<6>[    1.580000] usbcore: registered new interface driver ums-sddr09
<6>[    1.590000] usbcore: registered new interface driver ums-sddr55
<6>[    1.600000] usbcore: registered new interface driver ums-usbat
<6>[    1.600000] mice: PS/2 mouse device common for all mice
<6>[    1.610000] i2c /dev entries driver
<7>[    1.610000] cpufreq: Setting CPU Frequency to 800000 KHz
<7>[    1.610000] cpufreq: Setting PowerSaveState to off
<6>[    1.620000] sdhci: Secure Digital Host Controller Interface driver
<6>[    1.620000] sdhci: Copyright(c) Pierre Ossman
<5>[    1.630000] mmc0: mvsdio driver initialized, using GPIO 27 for card detection
<6>[    1.640000] usbcore: registered new interface driver usbhid
<6>[    1.640000] usbhid: v2.6:USB HID core driver
<6>[    1.650000] TCP cubic registered
<6>[    1.650000] NET: Registered protocol family 17
<6>[    1.660000] RPC: Registered udp transport module.
<6>[    1.660000] RPC: Registered tcp transport module.
<4>[    1.670000] drivers/rtc/hctosys.c: unable to open rtc device (rtc0)
<5>[    1.740000] UBIFS: recovery needed
<5>[    1.820000] UBIFS: recovery completed
<5>[    1.830000] UBIFS: mounted UBI device 0, volume 0, name "rootfs"
<5>[    1.830000] UBIFS: file system size:   110850048 bytes (108252 KiB, 105 MiB, 873 LEBs)
<5>[    1.840000] UBIFS: journal size:       9023488 bytes (8812 KiB, 8 MiB, 72 LEBs)
<5>[    1.850000] UBIFS: media format:       w4/r0 (latest is w4/r0)
<5>[    1.850000] UBIFS: default compressor: lzo
<5>[    1.860000] UBIFS: reserved for root:  0 bytes (0 KiB)
<4>[    1.860000] VFS: Mounted root (ubifs filesystem) on device 0:11.
<6>[    1.870000] Freeing init memory: 124K
<6>[    1.880000] usb 1-1: new high speed USB device using ehci_marvell and address 2
<6>[    2.050000] usb 1-1: configuration #1 chosen from 1 choice
<6>[    2.060000] scsi2 : SCSI emulation for USB Mass Storage devices
<7>[    2.070000] usb-storage: device found at 2
<7>[    2.070000] usb-storage: waiting for device to settle before scanning
<5>[    4.290000] eth0: link down
<5>[    4.290000] eth0: started
<5>[    5.840000] eth0: link up, full duplex, speed 1 Gbps
<5>[    7.070000] scsi 2:0:0:0: Direct-Access     SanDisk  Cruzer Fit       1.26 PQ: 0 ANSI: 5
<5>[    7.090000] sd 2:0:0:0: [sda] 31266816 512-byte logical blocks: (16.0 GB/14.9 GiB)
<5>[    7.100000] sd 2:0:0:0: [sda] Write Protect is off
<7>[    7.100000] sd 2:0:0:0: [sda] Mode Sense: 43 00 00 00
<3>[    7.100000] sd 2:0:0:0: [sda] Assuming drive cache: write through
<3>[    7.110000] sd 2:0:0:0: [sda] Assuming drive cache: write through
<6>[    7.120000]  sda: sda1
<5>[    7.120000] sd 2:0:0:0: Attached scsi generic sg0 type 0
<7>[    7.140000] usb-storage: device scan complete
<3>[    7.150000] sd 2:0:0:0: [sda] Assuming drive cache: write through
<5>[    7.160000] sd 2:0:0:0: [sda] Attached SCSI removable disk
<4>[    7.860000] IRQ 93 uses trigger mode 0; requested 3
<6>[    7.870000] input: gpio-keys as /devices/platform/gpio-keys.0/input/input0
<6>[    7.880000] xce_ebtn: Pogoplug series V4 eject button initialized.
<4>[    8.030000] ufsd: module license 'Commercial product' taints kernel.
<4>[    8.030000] Disabling lock debugging due to kernel taint
<5>[    8.070000] ufsd: driver (8.6 (U86_S[2012-02-28-18:39:23]), LBD=ON, delalloc, ioctl) loaded at bf00c000
<5>[    8.070000] NTFS support included
<5>[    8.070000] Hfs+/HfsX support included
<5>[    8.070000] For 'CloudEngines_PogoPlug_2011-08-03'
<4>[    8.400000] rtusb init rt2870 --->
<6>[    8.410000] usbcore: registered new interface driver rt2870
<4>[    8.440000] Cloud Engines XCE Init [Version: 3.9.0.4]
<6>[    8.440000] XCE: CPU MEMORY MAP:
<6>[    8.440000] XCE:   -- 0x00001000 - 0xbeffffff (3055 MB)  User Space Mappings
<6>[    8.450000] XCE:   -- 0xbf000000 - 0xbfffffff (  16 MB)  Kernel module space
<6>[    8.460000] XCE:   -- 0xc0000000 - 0xc7ffffff ( 128 MB)  Kernel direct-mapped ram
<6>[    8.470000] XCE:   -- 0xc8800000 - 0xe7ffffff ( 504 MB)  Kernel vmalloc space
<6>[    8.470000] XCE:   -- 0xe8000000 - 0xfeffffff ( 367 MB)  Kernel platform space
<6>[    8.480000] XCE: CPU FEATURES:
<6>[    8.480000] XCE:   -- I Cache:         enabled
<6>[    8.490000] XCE:   -- D Cache:         enabled
<6>[    8.490000] XCE:   -- Branch Predict:  disabled
<6>[    8.500000] XCE:   -- MMU:             enabled
<6>[    8.500000] XCE:   -- Alignment Abort: enabled
<6>[    8.510000] XCE: BLPARAMS:   -- Loading properties [c4d49efc].
<6>[    8.520000] XCE: BLPARAMS:   -- MTD @ [c45c1c00].
<6>[    8.520000] XCE: BLPARAMS: Locating parameter block...
<6>[    8.530000] XCE: BLPARAMS: reading 2048 bytes @ a0000
<6>[    8.530000] XCE: Loaded Property Size: 2048
<6>[    8.540000] XCE:    - 'cesvcid' -> '9C5FE2YZ96Z72G5C8AWKUNJHWW'
<6>[    8.540000] XCE:    - 'ceboardver' -> 'PPV4A3'
<6>[    8.550000] XCE:   -- ICache Prefetch: enabled
<6>[    8.550000] XCE:   -- DCache Prefetch: enabled
<6>[    8.560000] XCE:   -- L2 Cache:        enabled
<6>[    8.560000] XCE:   -- L2 Prefetch:     disabled
<6>[    8.570000] XCE:   -- L2 Writethrough: disabled
<6>[    8.570000] XCE:   -- Write Allocate:  disabled
<6>[    8.580000] XCE:   -- Streaming:       disabled
<6>[    8.580000] XCE: Current GPIO State:
<6>[    8.580000] XCE:  GPIO L OUT:    0x01f18400
<6>[    8.590000] XCE:  GPIO L OE:     0xfe004800
<6>[    8.590000] XCE:  GPIO L BLINK:  0x00000000
<6>[    8.600000] XCE:  GPIO L POL:    0x28000000
<6>[    8.600000] XCE:  GPIO L IN:     0x11f00000
<6>[    8.600000] XCE:  GPIO H OUT:    0x00000008
<6>[    8.610000] XCE:  GPIO H OE:     0x00000005
<6>[    8.610000] XCE:  GPIO H BLINK:  0x00000000
<6>[    8.620000] XCE:  GPIO H POL:    0x00000000
<6>[    8.620000] XCE:  GPIO H IN:     0x00000008
<6>[    8.720000] XCE: BLPARAMS:   -- Loading properties [c4babecc].
<6>[    8.720000] XCE: BLPARAMS:   -- MTD @ [c45c1c00].
<6>[    8.730000] XCE: BLPARAMS: Locating parameter block...
<6>[    8.730000] XCE: BLPARAMS: reading 2048 bytes @ a0000
<6>[    8.740000] XCE: BLPARAMS: reading 2048 bytes @ a0800
<6>[    8.750000] XCE: BLPARAMS: reading 2048 bytes @ a1000
<6>[    8.750000] XCE: BLPARAMS: reading 2048 bytes @ a1800
<6>[   14.370000] XCE: XCE: LED -> CONNECTED
<6>[   14.400000] kjournald starting.  Commit interval 5 seconds
<6>[   14.400000] EXT3 FS on sda1, internal journal
<6>[   14.410000] EXT3-fs: mounted filesystem with writeback data mode.
<6>[   14.730000] usb 1-1: reset high speed USB device using ehci_marvell and address 2

MISC: binary Galois Field multiplication

After reading NIST may not have you in mind, I decided that a new ISA should support binary Galois Field multiplication. Binary Galois Field is a special case of binary polynomial \( \mathbb{Z}_2[x] \) where addition and subtraction are already supported as XOR, written as \( \oplus \). What is missing for GF is multiplication and division in \( \mathbb{Z}_2[x] \). The binary polynomials are expressed as bit vectors where the \(n\)-th bit is the coefficient of the \(x^n\) term. Let \( \otimes \) be polynomial multiplication.

• pmul: \( (a, b) \to (r, s) \) where \( r s = a \otimes b \), i.e. \( r \) is the upper word of the result, and \( s \) is the lower word.
• pdiv.mod: \( (a, b) \to (q, r) \) where \( q \otimes b = a \oplus r \), i.e. \( q \) is the quotient and \( r \) is the remainder.

It's been a while since I last studied abstract algebra, so I might not have gotten all my terminology correct, but you get the idea.

MISC: a high-level comparison to TTA

There is this old saying that there is nothing new under the sun. While I thought I invented something new, it came to my attention the Transport Triggered Architecture (TTA) which I did not know before. I found some papers as early as 1994, by Henk Corporaal.

Both MISC and TTA specify an instruction set architecture where each ALU has associated input and output ports, and writing to the input ports trigger a computation.

MISC falls short describing how the instruction set would actually be implemented in hardware. It assumes that there is a hardware scheduler that can detect when the output port is ready and advances the pipeline. The compiler only needs to worry about transforming the program into a set of pipelines. This abstracts out the timing details such as gate length out of the instruction set architecture.

TTA programs consist of cycle-stepped move instructions that has to take gate length into account, due to the lack of a global control logic. If an operation requires two inputs—one is called the operand and the other is called a tigger—the operand must be stored before or during the same cycle as the trigger. If the program moves a value out of the result too early, it would read out a corrupt value. This means that the compiler has to take gate length into account while scheduling instructions. If a function unit takes too long (e.g. cache misses) to complete an operation, it must lock the data transport bus so additional move would not take place.

In contrast, MISC exposes no cycle-sensitive timing in the pipeline. The monadic design of the functional units allows pipelines to synchronize by data dependency graph, not by timing. Hence there is no need to globally lock the pipeline. I mentioned one instruction to wait for all moves in the instruction queue to finish, but I only added there for the purpose of context switching. I still need to elaborate more on how I plan to support preemptive multitasking.

TTA already has a hardware implementation. It is not clear if the idealized scheduler for MISC is implementable in hardware, or if it turns out to be the performance bottleneck.

MISC: Computation Modules

This is a continuation of Microcosmic Instruction Set Computer, defining the computation modules before I decide on the port assignments. The notation is \( (I_1, I_2, ..., I_m) \to (O_1, O_2, ..., O_n) \) for input ports \( I_1 ... I_m \) and output ports \( O_1 ... O_n \). The total number of input and output ports for each operator are kept as power of 2 to allow less fragmentation in port assignment later.

Arithmetic operators

• add: \( (a, b) \to (r, c) \) where \( r = a + b \) and \( c \) is the carry bit.
• sub: \( (a, b) \to (r, c) \) where \( r = a - b \) and \( c \) is the carry bit.
• neg: \( a \to b \) where \( b = -a \).
• mul: \( (a, b) \to (r, s) \) where \( r s = a \times b \), i.e. \( r \) is the upper word of the result, and \( s \) is the lower word.
• div.mod: \( (a, b) \to (q, r) \) where \( q \times b = (a - r) \), i.e. \( q \) is the quotient and \( r \) is the remainder.
• smul, sdiv.mod: same as mul and div.mod but for signed integers.
• and: \( (a, b) \to (c, c') \) where \( c = a \wedge b \) and \( c' = a \wedge \neg b \), both bitwise.
• or.xor: \( (a, b) \to (c, c') \) where \( c = a \vee b \) and \( c' = a \oplus b \), both bitwise.
• rot.left: \( (a, c) \to (r, s) \) where \( r \) is the result of shifting \( a \) to the left by \( c \) bits, and \( s \) is the overflow part of \( a \) adjacent to the least significant bit.
• rot.right: \( (a, c) \to (r, s) \) where \( r \) is the result of shifting \( a \) to the right by \( c \) bits, and \( s \) is the underflow part of \( a \) adjacent to the most significant bit.
• not: \( a \to b \) where \( b = \neg a \), bitwise.

Signed integers use two's complement representation, so they don't need to distinguish addition and subtraction. Note that the conditional branch instruction should be able to use the condition from the least significant bit which is the carry bit, as well as the most significant bit which is the signed bit. This allows comparing both signed and unsigned integers.

Convenience operators

• lea: \( (b, a, x) \to r \) computes \( r = 2^a \cdot x + b \).
• add3: \( (a, b, c) \to r \) computes \( r = a + b + c \).
• or3: \( (a, b, c) \to r \) computes \( r = a \vee b \vee c \).
• xor3: \( (a, b, c) \to r \) computes \( r = a \oplus b \oplus c \).

Any of these operators—especially “or” or “xor”—could be used for the purpose of joining the completion of all computations. These are not to be confused with non-deterministic join. A non-deterministic join is not necessary; just have two pipes connecting from some two different output ports to the same input port.

Conditional operators

• cond: \( (c, a, b) \to r \) where \( r = c \mathop{?}  a : b \), i.e. returns \( a \) if \( c \) is nonzero, otherwise \( b \).
• cx: \( x \to c \) where \( c \) extends the carry bit of \( x \) to fill the whole word.
• sx: \( x \to s \) where \( s \) extends the signed bit of \( x \) to fill the whole word.

Memory controller

• read: \( a \to r \) where \( r \) is the value of memory word at address \( a \) which must be word-aligned.
• write: \( (a, x, z) \to z' \) to write \( x \) to the memory word at address \( a \) which must be word-aligned, whenever \( z \) is also ready. The value of \( z \) is not used. When the write finishes, \( z' \) becomes ready with a zero value.
• cswap: \( (a, new, old) \to old' \) writes \( new \) to the memory word at address \( a \) only when \( a \) still contains the expected \( old \) value. The actual value of \( a \) before the swap is returned as \( old' \).

Byte packing

• pack: \( (a, b, p) \to r \) where \( r \) is the result of permuting the concatenation of \( a b \) according to mapping \( p \).
• unpack: \( (a, p) \to (r, s) \) where \( r \) and \( s \) are the two words selected from \( a \) by mapping \( p \) and they can be optionally sign extended.

Coprocessor I/O

• exec: \( (k, a_1, a_2) \to r \) sends a two-argument command to co-processor \( k \) and returns its result in \( r \).
• exec2: \( (k, a_1, a_2, a_3, a_4, a_5) \to (r_1, r_2) \) sends a five-argument command to co-processor \( k \) and returns a pair of results in \( r_1 \) and \( r_2 \).

This can be used to drive the floating point coprocessor as well. The floating point coprocessor, for example, would occupy a range of k in the coprocessor namespace, one for each operation.

Some concluding remark

The fact that all computation modules above have non-empty inputs and outputs means that this forms a monadic set of operators, where synchronization is accomplished by port pipelining. I guess you can call this Monadic Instruction Set Computer also.

Because of the fine granularity of some of the computation modules, it makes sense to base the cycle on the finest granule which is the gate distance, e.g. the bitwise operators are all single gate distance, hence single cycle. This means that while some modules are single cycle, others can be hundreds or thousands of cycles.

Microcosmic Instruction Set Computer

When it comes to instruction set architecture, there are many philosophies, ranging from CISC to RISC down to extremes like OISC or ZISC. The dominent is still Intel x86 or x86-64 which is CISC, but ARM is getting popular too which is RISC. I've not seen any commercial product based on OISC or ZISC so they are probably not practical.

Having had some experience in Internet planetary scale distributed computing where remote procedure calls are made between computer services, coming back to looking at instruction set design gives me the revelation that even a single-core microprocessor is itself a distributed system. Rather than a distributed system of disk storage, memcache, and web servers, the microprocessor is a distributed system of arithmetic logic units, memory controller, and I/O buses. This gives rise to the idea of a microcosmic instruction set computer where the instruction set takes care of basic register file and control flow, but offloads all computing and memory I/O activities to the microcosm of distributed services on the processor die.

The instruction set features:

• Some (yet-to-be specified) instructions for unconditional and conditional branching, namely to affect the instruction fetching.
• A small I/O address space (~16K?) each specifies a word-sized port, which are buffered memory that can be written to and read from. Each port also has a “ready” bit to signal the availability of data, for the purpose of instruction scheduling.
• Lower tiered I/O ports (0-15) are simply buffered general purpose register file. Middle tier ports (16-255) are for multiple ALUs, memory controllers, and external I/O controllers. Upper tier ports (256-?) are laid out in groups of 256 like the lower and middle tier ports (0-255) to enable additional instruction level parallelism.
• An instruction specifies a move from one source port to a destination port. The instruction is only executed when data for that port is ready, but multiple instructions can be queued by the instruction scheduler. The move instruction can be seen as “connecting” a pair of ports.
• An instruction to write a small constant value directly to a port.
• One instruction to wait for all moves in the instruction queue to finish.

All ports can be used like a register (i.e. they are buffered), but some ports are used for inputs and some are used for outputs. For example, an adder for \( i + j = k \) would occupy three ports, \( p_i \), \( p_j \), and \( p_k \). The adder begins working whenever the ready bits of \( p_i \) and \( p_j \) are set, and the ready bit of \( p_k \) is only asserted when the result is available. The adder can be powered off when it's not doing work.

The instruction scheduler could dynamically map port numbers in groups of 256 if it wishes to turn off additional die area to reduce power use even further.

Even within a single group, ports of the same functionality may indeed be a queue to a smaller number of units. For example, the port assignment might give \( 8 \times 3 = 24 \) ports to an adder, but a particular chip might only have 2 physical adders doing the work of 8 logical ones. It is particularly useful to have multiple logical units of memory controller to allow memory I/O to be queued.

To be continued...