Load Balancing of Parallelized Information Filters
Rowe, Neil C.
MetadataShow full item record
We investigate data-parallel implementation of a set of "informationfilters" used to rule out uninteresting data from a database or datastream. We develop an analytic model for the costs and advantages ofload rebalancing of the parallel filtering processes, as well as a quick heuristic for its desirability. Our model uses binomial models of the filter processes, and fits key parameters to results of extensive simulations. Experiments confirm our model. Rebalancing should pay off whenever processor communications costs are high. Further experiments showed it can also pay off even with low communications costs for 16-64 processes and 1-10 data items per processor; then imbalances can increase processing time by up to 52% in representative cases, and rebalancing can increase it by 78%, so our quick predictive model can be valuable. Results also show our proposed heuristic rebalancing criterion gives close to optimal balancing. We also extend our model to handle variations in filter processing time per data item.
This paper appeared in IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 2 (March/April 2002), 456-461.
Showing items related by title, author, creator and subject.
Son, Jun Hyeok (Monterey, California: Naval Postgraduate School, 2015-12);Focusing on potential economic development in Asia and acknowledging the stake of U.S. interests in the region, theUnited States has tried to foster secure international circumstances and promote cooperation among Asian ...
Walker, Thomas G. (Monterey, California: Naval Postgraduate School, 2015-12);To support the U.S. Administration’s announced rebalancing, or pivot, to the Asia-Pacific region, the U.S. Marine Corps is pushing its footprint beyond established logistics support locations. Yet, the Corps’ ability to ...
Analysis of the capabilities supporting Humanitarian Assistance and Disaster Relief operations of the Indonesian Navy (TNI AL) and theUnited States Marine Corps Marine Expeditionary Unit (USMC MEU) Achwandi, M. Reza; Hamler, Danny A.; Hoyt, Todd A. (Monterey, California: Naval Postgraduate School, 2015-12);The 2014 Quadrennial Defense Review emphasized the importance of the Humanitarian Assistance/Disaster Relief (HA/DR) mission in rebalancing the Asia-Pacific region. The coupling of the U.S. pivot to the Pacific and the ...