A Hierarchical Cache Coherent Protocol

As the number of processors in distributed-memory multiprocessors grows, efficiently supporting a shared-memory programming model becomes difficult. We have designed the Protocol for Hierarchical Directories (PHD) to allow shared-memory support for systems containing massive numbers of processors. PHD eliminates bandwidth problems by using a scalable network, decreases hot-spots by not relying on a single point to distribute blocks, and uses a scalable amount of space for its directories. PHD provides a shared-memory model by synthesizing a global shared memory from the local memories of processors. PHD supports sequentially consistent read, write, and test- and-set operations. This thesis also introduces a method of describing locality for hierarchical protocols and employs this method in the derivation of an abstract model of the protocol behavior. An embedded model, based on the work of Johnson[ISCA19], describes the protocol behavior when mapped to a k-ary n-cube. The thesis uses these two models to study the average height in the hierarchy that operations reach, the longest path messages travel, the number of messages that operations generate, the inter-transaction issue time, and the protocol overhead for different locality parameters, degrees of multithreading, and machine sizes. We determine that multithreading is only useful for approximately two to four threads; any additional interleaving does not decrease the overall latency. For small machines and high locality applications, this limitation is due mainly to the length of the running threads. For large machines with medium to low locality, this limitation is due mainly to the protocol overhead being too large. Our study using the embedded model shows that in situations where the run length between references to shared memory is at least an order of magnitude longer than the time to process a single state transition in the protocol, applications exhibit good performance. If separate controllers for processing protocol requests are included, the protocol scales to 32k processor machines as long as the application exhibits hierarchical locality: at least 22% of the global references must be able to be satisfied locally; at most 35% of the global references are allowed to reach the top level of the hierarchy.

Bubble Behavior in a Taylor Vortex

We present an experimental study on the behavior of bubbles captured in a Taylor vortex. The gap between a rotating inner cylinder and a stationary outer cylinder is filled with a Newtonian mineral oil. Beyond a critical rotation speed (ω[subscript c]), Taylor vortices appear in this system. Small air bubbles are introduced into the gap through a needle connected to a syringe pump. These are then captured in the cores of the vortices (core bubble) and in the outflow regions along the inner cylinder (wall bubble). The flow field is measured with a two-dimensional particle imaging velocimetry (PIV) system. The motion of the bubbles is monitored by using a high speed video camera. It has been found that, if the core bubbles are all of the same size, a bubble ring forms at the center of the vortex such that bubbles are azimuthally uniformly distributed. There is a saturation number (N[subscript s]) of bubbles in the ring, such that the addition of one more bubble leads eventually to a coalescence and a subsequent complicated evolution. Ns increases with increasing rotation speed and decreasing bubble size. For bubbles of non-uniform size, small bubbles and large bubbles in nearly the same orbit can be observed to cross due to their different circulating speeds. The wall bubbles, however, do not become uniformly distributed, but instead form short bubble-chains which might eventually evolve into large bubbles. The motion of droplets and particles in a Taylor vortex was also investigated. As with bubbles, droplets and particles align into a ring structure at low rotation speeds, but the saturation number is much smaller. Moreover, at high rotation speeds, droplets and particles exhibit a characteristic periodic oscillation in the axial, radial and tangential directions due to their inertia. In addition, experiments with non-spherical particles show that they behave rather similarly. This study provides a better understanding of particulate behavior in vortex flow structures.