Parallel Algorithms for Knapsack Type Problems

by Aleksandrov, V. N.; Megson, G. M.

• ISBN13: 9789810221201
• ISBN10: 9810221207
• eBook ISBN(s): 9789812817518
• Format: Hardcover
• Copyright: 1995-09-01
• Publisher: World Scientific Pub Co Inc
• More Book Details
• Purchase Benefits

Table of Contents

Introduction	1	(24)
Parallel computers: Two case studies	7	(3)
Systolic arrays	8	(1)
MIMD distributed memory organization	9	(1)
Basic Terminology	10	(5)
Knapsack Problems	15	(5)
The Dynamic programming approach	17	(3)
Previous and New Results	20	(5)
Linear Arrays	25	(24)
Linear systolic arrays	26	(5)
A modular case	29	(2)
Fixed sized linear systolic arrays	31	(10)
A Non-modular array for the UKP	32	(1)
Data partitioning and time estimation	33	(2)
A modular array for the UKP	35	(6)
Extension to other Knapsack Problems	41	(2)
The backtracking phase	43	(3)
Total time and observations	46	(3)
Probabilistic bounds	49	(18)
Introduction	49	(2)
Terminology and Problem Formulation	51	(4)
Designing the Linear Arrays	55	(7)
Mapping Technique	55	(2)
Allocation function	57	(1)
Timing function	57	(5)
Non-Modular array	62	(1)
The Ring	63	(1)
Mathematical Expectation of Time	64	(2)
A Uniform Distribution	64	(1)
An Exponential Distribution	65	(1)
Concluding remarks	66	(1)
Designing 2D Regular Arrays	67	(14)
Introduction	67	(2)
Terminology and Problem Formulation	69	(2)
A Fixed sized array	71	(5)
Further Improvements	76	(4)
Summary	80	(1)
Distributed Memory Implementation	81	(26)
Introduction	81	(1)
Dynamic programming approach for the KP	82	(1)
The MIMD distributed memory architecture	83	(1)
Parallel implementation	83	(7)
Data partitioning and data allocation	84	(2)
The parallel algorithm	86	(4)
Parallel execution time	90	(11)
Full column allocation	91	(6)
Wraparound allocation	97	(4)
PVM Implementation	101	(1)
Discussion and remarks	101	(6)
Mapping Integral Recurrences onto Regular Arrays	107	(48)
Introduction	107	(3)
Integral Recurrence Equations	110	(6)
Space-Time Mapping	116	(7)
Uniformisation	123	(15)
Uniformisation of Atomic Integral Recurrences: First Case	124	(3)
Uniformisation of Atomic Integral Recurrences: Second Case	127	(4)
Uniformisation and Affine Scheduling	131	(7)
Parametric Uniformisation	138	(8)
The Knapsack Problem	146	(6)
Conclusion	152	(3)
Mapping onto Fixed Size Arrays with Lower Dimensions	155	(24)
Introduction	155	(2)
The Knapsack Problem	157	(2)
Mapping Procedures	159	(5)
Run-Time Dependencies	164	(6)
Lower Dimensional Arrays	170	(5)
Code reconstruction	175	(3)
Summary	178	(1)
Comparison of Techniques	179	(6)
Heuristics vs Synthesis	179	(2)
Fixed size Arrays	181	(1)
Probablistic information	182	(1)
Performance	183	(2)
Bibliography	185