Performance evaluation of vector implementations of combinatorial algorithms

DOI10.1016/S0167-8191(84)90213-8MaRDI QIDQ1062729zbMATH OpenFDO

Authors Celso C. Ribeiro

Publication date 1985

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-8191(84)90213-8

zbMATH Keywords

binary knapsack problemcombinatorial algorithmsDijkstra-Floyd algorithmdynamic programmingperformance evaluationshortest path problemVector implementations

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Dynamic programming (90C39)

Review text

Vector implementations are proposed for the binary knapsack problem (dynamic programming) and the shortest path problem (Dijkstra's and Floyd's algorithm). Improvements in the performance due to the vectorization (CRAY-1) are reported, and seem to be in accordance with the discussion of a general model for performance evaluation.

Recommendations

• Experiments with parallel algorithms for combinatorial problems
• The vectorization of the partition problem
• scientific article; zbMATH DE number 882129
• scientific article; zbMATH DE number 4197775
• Vectorization and multitasking of dynamic programming in control: Experiments on a CRAY-2

Cited in

(3)

• An experimental study of improving performance by scalar replacement
• A note on applications of the `Vector Enumerator' algorithm.
• The vectorization of the partition problem

This page was built for publication: Performance evaluation of vector implementations of combinatorial algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062729)