https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Scalable parallel genetic algorithm for solving large integer linear programming models derived from behavioral synthesis
GC Shahid Beheshti University, Tehran, Iran.
GC Shahid Beheshti University, Tehran, Iran.
GC Shahid Beheshti University, Tehran, Iran.
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
2020 (English)In: Proceedings - 2020 28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2020, Institute of Electrical and Electronics Engineers Inc. , 2020, p. 390-394, article id 9092208Conference paper, Published paper (Other academic)
Abstract [en]

Solving Integer Linear Programming (ILP) models generally lies in the category of NP-hard problems. Therefore, as the size of ILP models grows, the efficiency of exact algorithms for solving the models reduced significantly and for large models it is not possible to have the result. Genetic Algorithm (GA) is a metaheuristic method capable of adjusting and redesigning parameters and operations according to the characteristics of ILP models. Still GA has huge search space for large models and parallelization is a suitable technique to tackle this problem. This paper presents a scalable parallel GA to solve large ILP models derived from behavioral synthesis of digital circuits. We show that although models have non-binary variables, only binary variables are sufficient for coding chromosomes. We also use 'unknown' values for some genes to decrease the likelihood of inconsistency in the encoded constraints. Our experiments verify the efficiency and scalability of the proposed algorithm on multicore platforms. The proposed method outperforms IBM ILOG CPLEX 12.6 and MI-LXPM algorithm where the ILP models include 550 to 2258 int / binary decision variables. Also, the results indicate that the saturation point of using parallel processing elements for solving the large ILP models is at least 60. 

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers Inc. , 2020. p. 390-394, article id 9092208
Keywords [en]
Behavioral synthesis, Integer linear programming, Parallel genetic algorithm, Chromosomes, Efficiency, Genetic algorithms, High level synthesis, NP-hard, Systems analysis, Decision variables, Exact algorithms, Integer linear programming models, Meta-heuristic methods, Multi-core platforms, Parallel genetic algorithms, Parallel processing elements, Integer programming
National Category
Embedded Systems
Identifiers
URN: urn:nbn:se:mdh:diva-48127DOI: 10.1109/PDP50117.2020.00066ISI: 000582555800059Scopus ID: 2-s2.0-85085505410ISBN: 9781728165820 (print)OAI: oai:DiVA.org:mdh-48127DiVA, id: diva2:1434877
Conference
28th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2020, 11 March 2020 through 13 March 2020
Available from: 2020-06-04 Created: 2020-06-04 Last updated: 2020-11-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Daneshtalab, Masoud

Search in DiVA

By author/editor
Daneshtalab, Masoud
By organisation
Embedded Systems
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 42 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf