On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs

A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript ∞]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript ∞]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript ∞]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript ∞]), but the work is increased by a factor of O(lg n).

On the Fabrication of Microparticles Using Electrohydrodynamic Atomization Method

A new approach for the control of the size of particles fabricated using the Electrohydrodynamic Atomization (EHDA) method is being developed. In short, the EHDA process produces solution droplets in a controlled manner, and as the solvent evaporates from the surface of the droplets, polymeric particles are formed. By varying the voltage applied, the size of the droplets can be changed, and consequently, the size of the particles can also be controlled. By using both a nozzle electrode and a ring electrode placed axisymmetrically and slightly above the nozzle electrode, we are able to produce a Single Taylor Cone Single Jet for a wide range of voltages, contrary to just using a single nozzle electrode where the range of permissible voltage for the creation of the Single Taylor Cone Single Jet is usually very small. Phase Doppler Particle Analyzer (PDPA) test results have shown that the droplet size increases with increasing voltage applied. This trend is predicted by the electrohydrodynamic theory of the Single Taylor Cone Single Jet based on a perfect dielectric fluid model. Particles fabricated using different voltages do not show much change in the particles size, and this may be attributed to the solvent evaporation process. Nevertheless, these preliminary results do show that this method has the potential of providing us with a way of fine controlling the particles size using relatively simple method with trends predictable by existing theories.