Journal
PROCEEDINGS OF THE 2019 IEEE CONFERENCE OF RUSSIAN YOUNG RESEARCHERS IN ELECTRICAL AND ELECTRONIC ENGINEERING (EICONRUS)
Volume -, Issue -, Pages 1821-1825Publisher
IEEE
DOI: 10.1109/eiconrus.2019.8657131
Keywords
Knapsack problem; Gray code; exhaustive search; parallel computation; load balancing
Categories
Funding
- Competitiveness Growth Program of the Federal Autonomous Educational Institution of Higher Education National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)
Ask authors/readers for more resources
In previous papers, we stated that splitting the lexicographic sequence into equal parts does not yield uniform workload distribution for a parallel computational system. One of the options we have considered is breaking the packing vectors space into classes based on the vectors' Hamming weight, and then split each of the classes into equal parts. In this paper, we investigate another load balancing technique based on using the Gray codes instead of the lexicographic sequence. As only one element of the packing changes on every step, we can calculate the packing weight dynamically. Thus, the time needed to weigh a packing becomes both shorter and more uniform. We study the properties of the Gray codes and analyze their impact on the algorithm run time and efficiency of parallel computation.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available