Welcome to the World!

My baby, Bryan Zhou Jiao, finally came to the world on Feb 15, 2011. Now I truly underdand how hard the ten-month long pregnancy is, which is especially true considering both my wife and me have passed the prime time for having a baby.
Fortunately the whole preganancy process basically went smoothly and both Mom and the baby are safe and healthy.
I am also a bit suprised so far. I am very afraid of baby crying and originally I though babies would cry very often. Luckily my little one is not worrisome and he only cried when he woke up and felt hungry, which seems to be his only requirement from us.

Here are some pictures. 

More photos and videos are available at Flickr.

GPGPU High Performance Computing using OpenCL -- Parallel Computing on Heterogeneous Platforms

The following technical discussion was co-authored with Lili Zhou who is a medical physics resident at NY Presbyterian Hospital / Weill Cornel Medical Center.
The discussion can help you understand the major hardware differences between multi-core CPUs and many-core GPUs (GPGPUs) and the different types of parallel workloads that CPUs and GPUs are each suited for.
Here it is.

Processing of large data sets entails parallel computing in order to achieve high throughput. Traditionally high throughput was only achievable through either proprietary hardware (Application-Specific Integrated Circuit (ASIC), Field-Programmable Gate Array (FPGA) or even Cell BE) or multi-node clusters.
However, as throughput-oriented multi-core processors become more pervasive, the same performance is now achievable through these commodity parallel architectures that range from multi-core CPU for low parallelism to many-core Graphics Processing Unit (GPU) for massive parallelism.

This article focuses on major hardware differences between CPU and GPU, which further decides the different workloads that each processor is suited for. In the end, it gives a data partition example using OpenCL across CPU and GPU, and compares the performance differences on the two platforms.

1 OpenCL – a New and Better Parallel Computing Paradigm

Because you most probably have different workloads that can be better processed using CPU than GPU or vice versa, you need to master parallel computing for both CPU and GPU.
However, parallel computing for heterogeneous processors is challenging as traditional programming paradigms for CPU and GPU are very different.

For example, you usually use POSIX Threads or Pthreads or OpenMP for CPU.
Although GPU typically only handles graphics computations, its gigaflops or even teraflops of floating point performance and high memory bandwidth make it suited to some non-graphics applications including data-intensive scientific and engineering computations, which actually falls into the scope of so-called General-Purpose Computing on Graphics Processing Unit (GPGPU).
However, GPGPU programming originally required programmers to possess intimate knowledge of graphics APIs (OpenGL or DirectX) and GPU architecture and to make their non-graphics applications look like graphics ones by mapping them into problems that drew triangles and polygons. This placed a great constraint for non-graphics domain scientists and engineers.
This old approach was adopted by Fang et al in the CT reconstruction algorithm.
With the advent of Unified Shaders, dedicated general purpose GPU such as the Telsa series from NVIDIA and the FireStream series from AMD, and high-level programming paradigms such as CUDA from NVIDIA and ATI Stream from AMD, CPU-based non-graphics applications can now directly access the tremendous performance of GPU without the above limitations.

Unfortunately all of the above different programming paradigms have very sharp learning curves and some are vendor-specific. Worse yet, none of them may be supported by future parallel processors.
OpenCL (Open Computing Language) is an open royalty-free standard for general purpose parallel programming across CPU, GPGPU, and such other processors as DSP and the Cell/B.E. processors, giving software developers portable and efficient access to the power of these heterogeneous processing platforms.
Although OpenCL is very new, it is a better choice because of the following factors:

• It utilizes a subset of ISO C99 with extensions for parallelism. You are probably already familiar with C programming;
•  You don’t need to learn anything else in order to take advantage of the parallel structures of current and even future parallel processors;
•  You just need to analyze your algorithms for data or tasks decomposition without even knowing the underlying complex multi-threaded programming mechanism, not to mention any graphics API or GPU internals.

We will use OpenCL terminologies in the following discussion. If you are not familiar with them, you are encouraged to read the first three chapters in the OpenCL specification documentation.

2 Major Differences between CPU and GPGPU in Parallel Computing

You need to know the major hardware differences to be able to select either CPU or GPGPU for different workloads. This discussion uses Dell Precision T7500 Tower Workstation (it has 2 Intel E5507 quad-core processors without Hyper-threading) and NVIDIA Tesla C2050 for reference. You can click their hyperlinks to get introductions for their capabilities. 
C2050 is based on NVIDIA’s next-generation CUDA architecture codenamed “Fermi” and has 14 CUDA 32-core multi-processors one of which is shown below courtesy of this resource:

2.1 GPGPU Supports Much More Hardware Threads than CP

T7500 only supports 8 hardware threads (4 compute units or core in CPU terms * 2 processors) while C2050 supports 21,504 (14 compute units or multi-processors in CUDA terms * 1536), which means C2050 is in a better position to process massive amounts of data in parallel than T7500.

2.2 GPGPU’s Threads Are Lightweight

By the above “hardware threads”, we mean the context or state of a processing element (one of the 4 compute units in T7500 or one of the 32 CUDA core in a C2050 compute unit) is saved in registers allocated to each thread so that context switching can be done in just one cycle.
If you create more than 8 threads for T7500, context switching will involve software operation, which takes many more cycles and are accordingly expensive and heavyweight.
Because C2050 has 32,768 registers, it can support as many as 21,504 in-flight hardware threads.

2.3 GPGPU’s SIMD and Global Memory Interface Is Much Wider than CPU’s

Single-Instruction Multiple-Data or SIMD is suited to process large data sets in batch mode.  T7500 implements SIMD with SSE that is 128-bit wide while C2050 implements SIMD with Single-Instruction Multiple-Thread or SIMT (a smallest execution unit of 32 threads runs a single instruction) that is 1024-bit wide.
T7500 has 192-bit global memory (system memory in CPU terms) interface through 3 parallel channels per processor while C2050’s memory interface is 384-bit through 6 channels.
This means C2050 is better suited to large data sets that possess spatial locality.

2.4 CPU Has Larger Cache and Lower Latency than GPGPU

T7500 has 32K L1 and 256K L2 per compute unit and 4M unified L3 while C2050 has 16K L1 per compute unit and 768K unified L2, which means that CPU is more lenient to the requirement on spatial locality than GPGPU and also has lower memory access latency than GPGPU.
However GPGPU is optimized for high-throughput by hiding the latency for memory access and other instructions through fast context switching to ready threads in the scheduling queue, which assumes, in addition to there being a large number of in-flight thread, the number of arithmetic operations per memory operation is also high (Imagine if you only perform one arithmetic per memory load, context switching doesn’t make much sense).

2.5 GPGPU Gives Developers Direct control over Its Fast On-chip Local Memory

GPGPU’s local memory (shared memory in CUDA terms) approximately corresponds to CPU’s L1 cache with respect to latency.
This memory region is shared by all work items (parallel threads) in a work group (a thread block), and can be used to boost effective bandwidth and system scalability by reducing or eliminating redundant loads from global memory and coalescing stride accesses to global memory.
The coalescing of strides is possible only when memory accesses of all work items in a work group fall into the local memory. In other words, a work group exhibits spatial locality in the local memory.

C2050 has 48K local memory. Without using it, the redundant global memory loads from tens of thousands of threads if they do exist, will cause too many memory bus contentions, and un-coalesced stride accesses will waste too much memory bandwidth.

2.6 Data Needs Transfer Between GPGPU and Host

T7500 uses Gen2 PCIe X 16 for data transfer. Although the bandwidth of Gen2 PCIe X 16 is 8GBps, it is much lower than C2050’s memory bandwidth 144GBps.
So the number of compute operations per data element transferred in your parallel algorithms should be high otherwise they might be better handled using CPU.

3 Different Workload Processing for CPU and GPGPU

A fundamental requirement for parallel computing on both CPU and GPGPU is that you data or tasks can be decomposed for concurrent processing. However CPU and GPGPU are suited to different types of workloads.
On the other hand, if your data or tasks exhibit little or no parallelism, you should leave them to CPU for serial processing. OpenCL allows you to parallelize parts of your CPU-based applications by putting the parallel parts into an OpenCL kernel while leaving the rest untouched.

3.1 GPGPU Is Better Suited to Process Large Data Sets

Small data sets can’t justify the time incurred by GPGPU’s slow data transfer on PCIe and other setup costs. Large data sets also spawn a large number of lightweight threads that are required in order to take full advantage of GPGPU’s massively parallel structure and to hide GPGPU’s the latency for memory access and other instructions by fast context switching.

3.2 GPGPU Requires the Number of Arithmetic Operations per Memory Operation Be High

This is to hide GPGPU’s long latency for memory access and other instructions. Otherwise CPU is a better choice thanks to its larger cache.

3.3 Data Transfer on PCIe Should Be Minimized

In other words the number of compute operations by GPGPU per data element should be high otherwise CPU is a better choice due to the low PCIe bandwidth.

3.4 Memory Access Should Have Spatial Locality

This appears more important to GPGPU than CPU because CPU has larger cache and GPGPU’s wider SIMD and memory interface otherwise only means waste of bandwidth and limited scalability across its compute units.

Please note that you can relax this requirement a bit for GPGPU if your parallel algorithm meets the above 3.2 very well because a large number of arithmetic operations do hide memory access latency. Actually this relaxation is also a winning point because in order to use CPU’s SIMD feature, you must explicitly pack your data into vectors, which requires your data to have perfect spatial locality.

4 Partition Your Data for Data Parallelism

The key to OpenCL programming is to partition your data or tasks so that they can be processed in parallel. Task parallelism needs to vectorize your data and / or to submit multiple small kernels.
Since you face data parallelism most of the time and it needs more data design consideration, this discussion will only deal with data parallelism.
Data parallelism allows you to concurrently apply the same OpenCL kernel (the function to run on GPU in parallel) to multiple independent work items (data elements) in an OpenCL index space (a memory object decomposed into data elements).  OpenCL doesn’t require you to have a one-to-one mapping between work items and data elements.

When you design a new parallel algorithm, you should put the requirements in Section 3 into consideration. A good candidate for parallelism is the FOR or WHILE loops with large iterations, and large data arrays.
One loop or one array can correspond to one dimension in an OpenCL index space while the loop iterations and array elements can map to work items. Nested loops or multi-dimension arrays can correspond to up to three dimensions in an OpenCL index space.

When you try to parallel an existing singled-threaded algorithm, you should also target its loops and data arrays and analyze its data access pattern to decide which processor is better suited, CPU or GPGPU?
If you are not sure about the selection, which is especially true when your existing algorithm doesn’t fit the requirements in Section 3 one way or the other (for example, the algorithm doesn’t possess too much spatial locality),  you can first parallelize it to CPU. Then you can enhance it to GPGPU with slight modifications (still remember that OpenCL is a general purpose parallel programming paradigm across CPU, GPGPU and other processors?) and compare them.

This approach is what we did for our CT image reconstruction program – Conebeam.
The Conebeam runs on Dell Precision T7500 Tower Workstation equipped with a NVIDIA Tesla C2050.  It has one one-dimensional input array, one one-dimensional output array, and three nested FOR loops that result in about 100M final iterations. The three FOR loops dynamically calculate the indexes for both arrays and compute the output array values based on the input array.
There are more than 200 arithmetic operations per memory access. Only the input and output arrays need transferring to and from GPGPU, respectively.

Here is pseudo-code method to parallelize on GPU:

01.void someMethod(float *inBuf, float *outBuf) {

02.    for(int angle=0; angle

03.      for (int binX=0; binX

04.        for (int binY=0; binY

05.          //the number of final iterations here is about 100M

06.          int idxIn = calculate based on angle,binX and binY;

07.          int idxOut = calculate based on angle,binX and binY;

08. 

09.          outBuf[idxOut] = calculate based on inBuf[idxIn];

10.        }

11.      }

12.    }

13.}

Because the three FOR loops calculate the values of the output array independently, they can be parallelized as the three dimensions in an OpenCL index space.
Because the three FOR loops have large iterations, and the two arrays are also large, this program seems to be a good candidate for GPGPU.
However, because the index accessing order of the two arrays is not synchronous with the three FOR loop iteration order, this program has very bad spatial locality and local memory can’t be used. Fortunately because it has high arithmetic operations per memory access, it should hide memory access latency in some degree if we use GPGPU.

Before we compare the two OpenCL implementations with real tests, here is some estimation:
Since T7500 has 8 compute units running at 2.2GHz while C2050 has 16 compute units running at 1.1GHz, T7500 has an approximate equivalent of 14 C2050 compute units.
T7500 has 192-bit global memory interface through 3 parallel channels per processor, so its overall memory interface is 384-bit. C2050’s memory interface is also 384-bit through 6 channels. 

The significant differences include (a) T7500 has just one processing element per compute unit while C2050 has 32 processing elements per compute unit; (b) T7500 has much larger cache than GPGPU and (c) T7500’s memory bandwidth is 230GBps while C2050 is 144GBps (GPU usually has higher bandwidth than CPU. However this high-end E5507’s effective memory speed is 4.8GHz while C2050 is only 3.0GHz).

The GPGPU version should be approximate 32 times faster than the CPU version if we put aside the cache factor and the CPU version doesn’t use SSE feature (The algorithm’s spatial locality is so bad that the above (c) shouldn’t generate any advantage to the CPU version).

Here are the real testing results:
The original single-threaded version ran about 70 minutes. The CPU version didn’t use SSE in order to port to NVIDIA GPGPU version easily and it ran about 12 minutes. The GPGPU version ran about 1 minute.
The CPU version didn’t have 8 times improvement over the single-threaded version because the Conebeam doesn’t have spatial locality and the 4 cores per processor incur memory bus contentions.
The GPGPU version didn’t have 32 times improvement over the CPU version because again the Conebeam doesn’t have spatial locality and CPU has much large cache.
In order to have linear scalability on GPGPU, the algorithm should be enhanced to exhibit spatial locality if it is possible.

5 Further Discussion

A major challenge for GPU programming is to preserve GPU performance levels while increasing the generality and expressiveness of application interfaces.
Although OpenCL, CUDA and ATI Stream relieve programmers from learning graphics jargons, they may not allow you to make good use of all GPU resources.  The authors are not sure whether this concern still hold true even with NVIDIA’s Telsa series and AMD’s FireStream series.

While OpenCL provides programming portability, it doesn't necesssarily provide performance portability.

GPGPU High Performance Computing using OpenCL -- Work with Multiple Vendor Platforms using ICD

Sometimes you have different workloads that are better handled with different vendor OpenCL implementations.
For example if your data presents access locality or coherence, the number of calculation per data element transferred on PCI  is high and the number of calculation per memory access is also high, you can use NVIDIA's OpenCL implementation on its GPGPU.
On the other hand, if your data doesn't possess all of the characteristic mentioned above, you can use ATI/AMD's OpenCL implementation on CPU so that you at least can take advantage of all your CPU cores.

OpenCL has an extension "cl_khr_icd". It is technically called OpenCL ICD (Installable Client Driver) that is a means of allowing multiple OpenCL implementations to co-exist and applications to select between them at runtime.

In my case since I have both CPU and GPGPU-friendly data, I installed on a 64-bit Windows 7 workstation both NVIDIA GPU Computing SDK 3.2 that support OpenCL 1.0, and ATI Stream SDK 2.2 that support OpenCL 1.1.

1. Find out whether your Vendor's SDK Supports OpenCL ICD
You can compile and run NVIDIA's oclDeviceQuery program. If you see "cl_khr_icd" in section "CL_DEVICE_EXTENSIONS" it means NVIDIA supports Opencl ICD.
You can also run ATI's "clinfo" program. It actually prints out all OpenCL platforms. Again if you see "cl_khr_icd" in section "Extension" it means the corresponding platform supports Opencl ICD.

2. How does ICD Work?
Although I setup all my Visual Studio projects with NVIDIA GPU Computing SD, I basically can still dynamically load ATI's CPU OpenCL implementation.
The project setup basically needs two configurations. One is to specify the OpenCL include directory that contains vendor-neutral headers such as cl.h, cl_ext.h and some vendor-specific headers such as cl_agent_amd.h for AMD.
Unless your SDK's have different OpenCL versions, all vendor-neutral headers should be the same. If you need vendor-specific headers, of course you have to setup your project with that vendor's SDK.

The other configuration is to specify the OpenCL library directory where a vendor-neutral stub library "OpenCL.lib" is located. This "OpenCL.lib" is called ICD loader that is responsible to dynamically load a vendor specific ICD library.
When you install a OpenCL SDK, the SDK registers its ICD DLL in the register key
HKEY_LOCAL_MACHINE\SOFTWARE\Khronos\OpenCL\Vendors on Windows if it supports ICD.
So the ICD loader can scan the above register key and dynamically load your vendor's DLL library.

For more information, please refer to this resource. 

3. How does ICD affect your Code?
Your application is now responsible for selecting which of the OpenCL platforms present on a system it wishes to use, instead of just requesting the system default.
This means using the clGetPlatformIDs() and clGetPlatformInfo() functions to examine the list of available OpenCL implementations and selecting the one that best suits your requirements.

For example, previously you could call the following function without specifying the specific platform value:
context = clCreateContextFromType(
     0, CL_DEVICE_TYPE_GPU, NULL, NULL, &status);

With ICD, you must specify a specific platform:

cl_context_properties cps[3] = {
              CL_CONTEXT_PLATFORM,
              (cl_context_properties)platform,
              0};
context = clCreateContextFromType(
     cps, CL_DEVICE_TYPE_GPU, NULL, NULL, &status);

GPGPU High Performance Computing using OpenCL -- Installation and Setup

High Performance Computing (HPC) with General-Purpose GPU or GPGPU is one of the hottest technologies when it comes to massive amount of data processing.
Compared to the general-purpose CPU, GPGPU adapts some innovative new approaches to parallel computing both from software and hardware perspective.

When it comes to program GPGPU, OpenCL is the clear choice because it is the open standard for writing programs that execute across heterogeneous platforms consisting of CPUs, GPUs, and other existing or future processors. And almost all major GPU vendors including Nvidia and AMD(ATI) support it, which was manifested by their OpenCL 1.0 driver releases recently.

I have been studying GPGPU for several months. Now I get a real chance to help some scientists process some medical image data. Here are what I have.

• 64-bit Windows 7 professional;
• Dell Precision T7500 Tower Workstation. It includes 2 Intel's latest 64-bit Xeon quad-core processors (a total of 8 physical cores. no HyperThreading), 6GB DDR3 ECC main memory, Broadcom NetXtreme 57xx Gigabit NIC, and ATI Firepro 3D V5800 for the display.
• Nvidia Tesla C2050 GPGPU. It has 448 CUDA cores and 3G GDDR5 ECC global memory. It is Nvidia's flagship product to build a powerful workstation.

1. Install C2050
You can really build a personal supercomputer (or a mini-cluster) right on you desk using T7500 and C2050. Unfortunately T7500 and C2050 came separately and installing C2050 on T7500 is not that straightforward as what the C2050 installation instructions tell you inside its CD package.

With C2050 you can basically configure 2 ways:

1. Keep the existing ATI Firepro as the display adapter and the new C2050 as a pure computing co-processor (not use it to drive display). 
2. Use C2050 as both the display adapter and a computing co-processor.

Configuration 1 is my case. I believe many people also want to have this configuration.

The first step in the C2050 installation instructions is to remove current graphics driver. This should only work for configuration 2.
My first attempt strictly followed the instructions. I downloaded and installed the latest Nvidia driver 263.06 and its GPU Computing SDK 3.2. My monitor was still connected to the FirePro adapter. The Windows Device Manager shows a standard VGA adapter and Tesla C2050 adapter both of which are working properly.
However when I ran the oclDeviceQuery OpenCL example in the SDK, C2050 was not recognized.
I am not sure whether it will work if I connect the monitor to C2050 and disable the standard VGA driver. I didn't put any more effort into it because I really want to have configuration 1.

So my next attempt was to restore the ATI Firepro driver. Unfortunately my previous uninstalling did some damage and I couldn't restore the ATI Firepro driver even the installation files still seem to be under c:\drivers\video\R259137\packages\drivers. So I downloaded the latest FirePro V5800 driver package on AMD's website and finally restored.
Now when I tried to run the same oclDeviceQuery, I got the same result. Actually even when you try to run any of the CUDA examples in the SDK, it didn't work neither.

In order to make C2050 recognized, you need to enable it to work in the so called TCC (Telsa Computing Cluster) mode instead of the WDDM mode. Basically the TCC mode enables the Tesla C2050 to work as a computing co-processor along with a display adapter among other functions.
Nvidia's release document for C2050 driver is so confusing at this point. The document mentions TCC is the default mode for C2050 that made me think it would be in TCC mode when I installed it. But it is not in my case.

I tried to run nvidia-smi to enable TCC mode but it complained there was no TCC GPU detected.
In order to enable TCC mode, you have to manually edit the Windows registry by adding a DWORD entry called "AdapterType" and setting its value to 2. This new entry should be under
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\ Class\{4D36E968-E325-11CE-BFC1-08002BE10318}\0001 (or 0000 or whatever number that corresponds to your C2050 adapter).
After the above change, you have to reboot. After reboot, when you can run the same oclDeviceQuer, you will see Telsa C2050 is successfully recognized.
Please be noted that because TCC mode disable the graphical functions, none of graphical examples will work.But isn't this what you want? The TCC mode is faster than the WDDM mode for computing and let the display adapter to do graphics.

2. OpenCL Support By Tesla C2050 Driver
Another confusing point in the C2050 driver release document is it didn't mention to support OpenCL. It only says to support CUDA C/C++. Fortunately the testing with its OpenCL examples show it indeed supports OpneCL 1.0 (actually if you examine the files installed by the 263.06 driver package, you can find the opencl.dll library).

3. Install OpenCL SDK
Nvidia's Developer Zone also seem to be confusing. When I just want to setup a computing SDK for GPGPU(not graphics), I was at loss what to download.
Basically you have to download 2 SDKs after you have installed the C2050 Driver (the driver package includes both the low level CUDA driver and OpenCL driver).

1. NVIDIA GPU Computing Toolkit. It includes both CUDA and OpenCL SDKs.
2. NVIDIA GPU Computing SDK 3.2. It includes SDSs for CUDA, OpenCL and DirectComput. It also include samples.

For OpenCL development, you only need to install 2.
On Windows 7, you probably have Visual Studio 2010. However the OpenCL example solution in the above 2 is for Visual Studio 2005 and 2008 only. The good news is Visual Studio 2010 can successfully convert the 2008 solution. The only major conversion warning is regarding the targetName is not consistent with the generated executable file name. But this will not cause you any trouble.

Commercial-Off-The-Shell Enterprise Real Time Computing (COTS ERTC) -- Part 4: Network Requirements

Enterprise applications rarely work in isolation nowadays. Instead they usually cooperate with one another in a network environment.
Due to Ethernet's uniqueness, this topic will only discuss the TCP/IP suite over Ethernet. The networks in Figure 4.1 are used for the discussion.

Figure 4.1 Networks

1. Network Latency
The network latency from a host in LAN1 such as Host11 to a host in LAN2 such as Host21 is the cumulative latency of all the following component:

• the TCP/IP stack latency on Host11. It includes all OSI layers except the 7th application layer (you have full control at the application layer). At least the 2 lower layers are implemented in the NIC firmware. All other layers are either included in the OS or also included in the NIC firmware.
• the switch latency in LAN1. The switch is a Layer 2 device. Originally an unintelligent Layer 1 hub or repeater was used. I will compare the latency difference later on.
• the routers latencies between LAN1 and LAN2. The routers are actually Layer 3 switches.
• the switch latency in LAN2. Again the switch is a Layer 2 device.
• the TCP/IP stack latency on Host21. Again it includes all OSI layers except the 7th application layer.
• the propagation delay from Host11 to Host21. It is the time it takes for signals to travel in the physical copper cables or fibers. Signals in fibers or copper cables can travel at about 2/3 of the fundamental speed of light.
  If the communication distance is short e.g. in a LAN, the propagation latency can be negligible compared to other larger latencies.
  On the other hand if the the communication distance is long, it can't be ignored. For example the straight distance from San Francisco to New York is about 4,125 kilometers and the one-way signal travel needs about 19.6ms that is the lower bound of your overall latency optimization.

Network latency can also be defined as the round-trip latency between Host11 and Host12. However since our discussion focuses on latency and jitter analysis of all involving components, the above one-way definition is sufficient.

The data unit in our discussion is a packet. For example we can set it anywhere from the minimum Ethernet frame size (it is about 64 bytes) to the maximum MTU (it is about 1500 bytes) and compare the difference.
When you analyze your application level latency, the data unit is an application level request, which has complications when interacting with the underlying Maximum Segment Size (MSS) of TCP and the MTU of Ethernet frames (later sections will explain more details).

The prioritized latency and jitter analysis mentioned in Part 1 still applies here. For example upgrading to a faster switch in San Francisco doesn't make sense because the minimum latency to New York is bounded by the 19.6ms propagation delay and the latency of switches is usually in low micro-seconds.

The following sections will discuss the latency and jitter in all involving components.
2. Non-Determinism in Ethernet
Ethernet, as standardized by IEEE 802.3, is implemented at Layer 1 and 2 of the OSI model. Its latency comes from the processing delays at  Layer 1 and 2. The latency has jitter because of its media access control (MAC) protocol - CSMA / CD at Layer 2.

With CSMA / CD, each host detects if another host is transmitting in the shared medium before it tries to transmit its own data (Carrier Sense). When a host detects a carrier, its Carrier Sense is turned on and it will defer transmission until determining the medium is free. This deference is unfortunately not predicable. If two hosts happen to transmit simultaneously (Multiple Access), a collision occurs and all frames are destroyed.

If we replace the switch in LAN1 / LAN2 with a hub / repeater, all four hosts will be in one collision domain. The more hosts trying to send data, the more collisions and the more non-deterministic.
Hosts sharing a half duplex connection are also in the same collision domain.For example even there are only Host11 and Host12 communicating to each other using a half duplex connection in LAN1, collisions still happen when Host11 and Host12 tries to send data to each other concurrently.

Although redesign of MAC protocol can solve the collision problem, it is not compatible to the existing ubiquitous Ethernet deployments and thus is appropriate and not a COTS solution.
If we can avoid collision, Ethernet will be much deterministic. This is what the switch in LAN1 / LAN2 is supposed to do. With the switch each host is guaranteed the exclusive use of the medium in both directions and is thus in a different collision domain from other hosts.
For example Host11 can communicate with Host12 while Host13 is communicating with Host14 without causing any collisions or frame drops.

3. Non-Determinism in TCP/IP
IP is at Layer 3; TCP and UDP are at Layer 4. The biggest jitter at these upper layers actually comes from the non-determinism of the underlying CSMA / CD.
For example if the underlying frame was dropped due to collision, the upper packet will be lost if it is UPD and will be retransmitted if it is TCP thanks to TCP's time-out mechanism.

A side note for TCP's time-out mechanism: if the network is slow, a low time-out value can lead to false retransmission. This is another reason why RTC applications prefer such fast networks as LAN.

You should also be aware of the following points
3.1 Non-Deterministic Routing Paths
A router has an additional Layer 3 compared to a switch. The more routers, the more potential communication paths between LAN1 and LAN2, and the more non-deterministic. A long communication path also leads to more frame drops due to data corruption. So a RTC system is usually enclosed in a LAN; otherwise make sure your routing path is deterministic.This is why many algorithmic trading systems especially high-frequency trading system, collocate with exchanges.

If the communication path is predicable, the determinism of a network with switches and routers will depend on that of those switches and routers. Modern switches and routers are actually very fast and can show very low jitter if managed properly, which will be discussed in Section 4.
.
3.2 Packet Header Overhead and Fragmentation
Each packet at IP, UDP and TCP layers has a header besides the real payload. The head size for IP, UDP and TCP is 20, 8 and 20, respectively.
Actually the Ethernet frame at Lay 2 also has a 20 bytes overhead. When an IP packet is greater than the Ethernet MTU (it is about 1500 bytes), IP needs to fragment and reassemble its packet.
TCP also fragments its stream into packets based on the MSS, the available window size and some other factors.

On one hand, more fragmentation and reassembly means more extra computing and higher latency. On the other hand, smaller packets than the MTU or MSS mean more significant header overhead and lower throughput.
In order to reduce jitter, your application level requests shouldn't have too variant sizes (different sized requests also mean different transmission delay). You should make your requests as large as possible before the latency misses your target. If possible, please decide the request size based on MTU.

3.3 TCP Flow Control
In order to avoid TCP packet drops from buffer overflows, TCP employs a sliding window mechanism to control its data flow.
So slow processing at the receiver host requires the sender host to send out smaller packets or even have to wait if the window size becomes 0. In order to reduce this jitter, make sure both ends can process network data fast and predictably.

If the network is slow, the sender may have to wait for the latest window size from the receiver. A fast network such as LAN can reduce this waiting latency. 

3.4 Nagle's Algorithm
Because of the 20 bytes header overhead in TCP, Nagle's algorithm coalesces a number of small outgoing messages into one packet and sends it out.
This algorithm is usually unacceptable to RTC systems because they need immediate response for each of their requests. This is especially true when the RTC requests are small.

RTC systems usually take the following two counter-measures:

• Enclose each request in one TCP packet;
• Turn off this algorithm by using the TCP_NODELAY socket option.

3.5 Delayed Acknowledgment
Again because of 20 bytes header overhead in TCP, a pure TCP response packet will have too much overhead. So this mechanism delays the TCP layer response by waiting about one or two hundred milliseconds, and hopes to send back the response along with the upper application layer response using just one TCP packet instead of two.

Unfortunately a one or two hundred milliseconds deadlock can occur if this mechanism interacts with the Nagle's algorithm and your application's response doesn't synchronize with the TCP layer's e.g. an application request was sent out in two or more TCP packets. Please refer to this resource for a detailed analysis.

In order to avoid this jitter, you need to take one or more of the following measures:

• disable the Nagle's algorithm;
• disable or configure the delayed acknowledgment mechanism. Please refer to this resource on Windows; and TCP_QUICKACK on Linux;
• Make sure your application level request is enclosed in one TCP packet.

3.6 UDP with Application Level Retransmission and Flow Controls
TCP implements its reliability at the cost of more computing work and header overhead than UDP. If TCP's reliability is more than what you want, you can use UDP and implement your simple reliability by yourself at the application layer. This approach should give your lower latency and jitter than using TCP.

4. Latency and Jitter of a Switch / Router
A router has an additional Layer 3 function. Its processing latency in a well-planed network will be predicable through a warm-up period that should cache all routing paths in the router. So we will focus on switches only.
A modern switch basically has two packet forwarding methods:

• Store and forward. A whole frame is buffered before being forwarded. A checksum is usually performed on each frame.
• Cut through. The switch reads only up to the frame's hardware address before starting to forward it. There is no error checking.

Because a cut-through switch doesn't have the additional buffering step, it has even shorter latency. However a cut-through switch will fall back to store and forward if its outgoing (egress) port is busy at the time a frame arrives. So we will focus on store-and-forward switches.

The one-way port-to-port latency of a switch is the cumulative delays of the following components:

• Layer 1 processing at both ports including signal modulation and data framing;
• Switch Fabric Latency. A switch has an internally shared high-bandwidth fabric that is much faster than any of its ports.
• Store and forward latency;
• Queuing latency. It occurs when different ingress ports are sending frames to the same egress port concurrently. Since only one frame can be transmitted at a time from the egress port, the other frames must be queued for sequential transmission in a FIFO manner. This phenomenon is called head-of-line blocking. Due to the FIFO behavior, the latency of a frame in the queue is unpredictable.
  So each port of a switch has an outgoing queue, which along with the switch fabric actually gives the impression of simultaneous paths among its multiple ports. 

Detailed analysis can be found from these two resources: Switched Ethernet Latency Analysis and Latency on a Switched Ethernet Network.

Both analyses show the queuing latency is usually the largest and a switch's jitter comes from it due to its unpredictable head-of-line blocking. .
In order to reduce the queuing latency and jitter, you need to take one or more of the following measures:

• Plan your network traffic properly including a predicable many-to-one mapping from ingress ports to egress ports; a smaller many-side value if a higher predictability is needed; and more importantly, no egress port should be oversubscribed.
  For example if you egress port is of 10GbE, you can only have a maximum of 10 1GbE ingress ports concurrently sending data to it; otherwise frame loss will occur. If you need some 1GbE port to have a higher predictability, you need to reduce the number of 1GbE ingress ports concurrently sending data to the 10 GbE egress port. 
• Because a switch's queuing jitter can cause avalanche effect at subsequent  network hops, this is another reason why you need to reduce the number of routers in your networks;
• Apply Virutal Lan (VLAN) or Priority values to different traffic. Make sure your RTC frames are in a separate VLAN or have the highest priority. This is similar to the different priority levels for RTC threads we discussed in Part 3. 

Finally in this section, even a hub / repeater has lower latency than a switch thanks to its simple Layer 1 processing, a RTC system should not use it unless necessary such as port mirroring because it creates jitter.

5. Gigabit Ethernet
Ethernet evolved from 10BASE-T to 100BASE-T to the current widely deployed 1GbE or Gigabit Ethernet. Now even 10GbE has often been seen in backbone networks and high-end servers as a cheaper alternative to the appropriate and expensive high-speed interconnects such as Fiber Channel and InfinitBand.
A modern cut-through 10GbE switch such as BLADE'S RackSwitch G8124 can has an average port-to-port latency in 680 nanoseconds (the average is on latencies of several different packet sizes from the minimum 64 bytes to the maximum 1518 bytes).

Although this 680 nanoseconds latency is at the same magnitude as the main memory, the load on CPU increases linearly, without some kind of TCP offloading or OS kernel bypassing, as a function of packets processed, with the usual rule of thumb being that each bit per second of bandwidth consumes about a HZ of the CPU clock. For example 10Gbs of network traffic consumes about 10GHz of CPU that is much higher than the 3.33GHz of Intel's latest processor Core i7.
As more of the host CPU is consumed by the network load, both CPU utilization and host send / receive latency and jitter become significant issues.
RDMA over TCP/IP or iWARP has come up as a rescue. Basically an iWARP NIC or R-NIC allows a server to read/write data directly between its user memory space and the user memory space of another R-NIC-enabled host on the network without any involvement of the host operating systems.

API's have been implemented for different platforms including the OpenFabrics Enterprise Distribution (OFED) by the OpenFabrics Alliance for Linux operating system, and the Winsock Direct protocol for Microsoft Windows.