The problem of online job scheduling on various parallelarchitectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorit...
详细信息
The problem of online job scheduling on various parallelarchitectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given.< >
The proceedings contain 45 papers. The topics discussed include: fast parallelalgorithms for the unit cost editing distance between trees;towards understanding exclusive read;on the parallel complexity of integer pro...
ISBN:
(纸本)089791323X
The proceedings contain 45 papers. The topics discussed include: fast parallelalgorithms for the unit cost editing distance between trees;towards understanding exclusive read;on the parallel complexity of integer programming;parallel RAMs with bounded memory wordsize;load balancing, selection and sorting on the hypercube;the power of parallel pointer manipulation;the communication complexity of several problems in matrix compntation;embedding of d-dimensional grids into optimal hypercubes;deterministic P-RAM simulation with constant redundancy;processor networks and interconnection networks without long wires;a lower bound on the size of shellsort sorting networks;cost-bandwidth tradeoffs for communication networks;a more practical PRAM model;the APRAM: incorporating asynchrony into the PRAM model;fault tolerance in hypercube-derivative networks;square meshes are not always optimal;parallel graph contraction;and the virtual time machine.
暂无评论