Efficient linear systolic array for the knapsack problem

Rumen Andonov 1 Patrice Quinton 1
1 API - Parallel VLSI Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : A processor-efficient systolic algorithm for the dynamic programming approach to the knapsack problem is presented in this paper. The algorithm is implemented on a linear systolic array where the number of cells q, the cell memory storage a and the input/output requirements are design parameters. These are independent of the problem size given by the number of the objects m and the knapsack capacity c. The time complexity of the algorithm is Q(mc/q+m) and both the time speedup and the processor efficiency are asymptotically optimal. A new procedure for the backtracking phase of the algorithm with a time complexity Q(m) is also proposed. It is an improvement on the usual strategies used for back-tracking which have a time complexity Q(m+c).
Type de document :
Rapport
[Research Report] RR-1661, INRIA. 1992
Liste complète des métadonnées

https://hal.inria.fr/inria-00074896
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:39
Dernière modification le : jeudi 11 janvier 2018 - 06:20:08
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:57:51

Fichiers

Identifiants

  • HAL Id : inria-00074896, version 1

Collections

Citation

Rumen Andonov, Patrice Quinton. Efficient linear systolic array for the knapsack problem. [Research Report] RR-1661, INRIA. 1992. 〈inria-00074896〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

162