1 Ocak 2020 Dergi makalesi Açık Erişim

Karahoda, Sertac; Erenay, Osman Tufan; Kaya, Kamer; Turker, Uraz Cengiz; Yenigun, Husnu

DataCite XML

<?xml version='1.0' encoding='utf-8'?>
<resource xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://datacite.org/schema/kernel-4" xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4.1/metadata.xsd">
  <identifier identifierType="URL">https://aperta.ulakbim.gov.tr/record/8337</identifier>
  <creators>
    <creator>
      <creatorName>Karahoda, Sertac</creatorName>
      <givenName>Sertac</givenName>
      <familyName>Karahoda</familyName>
      <affiliation>Sabanci Univ, Fac Sci &amp; Engn, Comp Sci &amp; Engn, Istanbul, Turkey</affiliation>
    </creator>
    <creator>
      <creatorName>Erenay, Osman Tufan</creatorName>
      <givenName>Osman Tufan</givenName>
      <familyName>Erenay</familyName>
      <affiliation>Sabanci Univ, Fac Sci &amp; Engn, Comp Sci &amp; Engn, Istanbul, Turkey</affiliation>
    </creator>
    <creator>
      <creatorName>Kaya, Kamer</creatorName>
      <givenName>Kamer</givenName>
      <familyName>Kaya</familyName>
      <affiliation>Sabanci Univ, Fac Sci &amp; Engn, Comp Sci &amp; Engn, Istanbul, Turkey</affiliation>
    </creator>
    <creator>
      <creatorName>Turker, Uraz Cengiz</creatorName>
      <givenName>Uraz Cengiz</givenName>
      <familyName>Turker</familyName>
      <affiliation>Univ Leicester, Dept Informat, Leicester, Leics, England</affiliation>
    </creator>
    <creator>
      <creatorName>Yenigun, Husnu</creatorName>
      <givenName>Husnu</givenName>
      <familyName>Yenigun</familyName>
      <affiliation>Sabanci Univ, Fac Sci &amp; Engn, Comp Sci &amp; Engn, Istanbul, Turkey</affiliation>
    </creator>
  </creators>
  <titles>
    <title>Multicore And Manycore Parallelization Of Cheap Synchronizing Sequence Heuristics</title>
  </titles>
  <publisher>Aperta</publisher>
  <publicationYear>2020</publicationYear>
  <dates>
    <date dateType="Issued">2020-01-01</date>
  </dates>
  <resourceType resourceTypeGeneral="Text">Journal article</resourceType>
  <alternateIdentifiers>
    <alternateIdentifier alternateIdentifierType="url">https://aperta.ulakbim.gov.tr/record/8337</alternateIdentifier>
  </alternateIdentifiers>
  <relatedIdentifiers>
    <relatedIdentifier relatedIdentifierType="DOI" relationType="IsIdenticalTo">10.1016/j.jpdc.2020.02.009</relatedIdentifier>
  </relatedIdentifiers>
  <rightsList>
    <rights rightsURI="http://www.opendefinition.org/licenses/cc-by">Creative Commons Attribution</rights>
    <rights rightsURI="info:eu-repo/semantics/openAccess">Open Access</rights>
  </rightsList>
  <descriptions>
    <description descriptionType="Abstract">An important concept in finite state machine based testing is synchronization which is used to initialize an implementation to a particular state. Usually, synchronizing sequences are used for this purpose and the length of the sequence used is important since it determines the cost of the initialization process. Unfortunately, the shortest synchronization sequence problem is NP-Hard. Instead, heuristics are used to generate short sequences. However, the cubic complexity of even the fastest heuristic algorithms can be a problem in practice. In order to scale the performance of the heuristics for generating short synchronizing sequences, we propose algorithmic improvements together with a parallel implementation of the cheapest heuristics existing in the literature. To identify the bottlenecks of these heuristics, we experimented on random and slowly synchronizing automata. The identified bottlenecks in the algorithms are improved by using algorithmic modifications. We also implement the techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel computation architectures. The sequential implementation of the heuristic algorithms are compared to our parallel implementations by using a test suite consisting of 1200 automata. The speedup values obtained depend on the size and the nature of the automaton. In our experiments, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. Furthermore, the proposed methods scale well and the speedup values increase as the size of the automata increases. (C) 2020 Elsevier Inc. All rights reserved.</description>
  </descriptions>
</resource>