Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines
A Master of Science thesis in Computer Engineering by Mustafa Ali entitled, "Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines," submitted in February 2015. Thesis advisor is Dr. Gerassimos Barlas and thesis co-advisor is Dr. Khaled El-Fakih. Soft and hard copy...
Saved in:
| Main Author: | |
|---|---|
| Format: | doctoralThesis |
| Published: |
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/11073/7788 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513442081144832 |
|---|---|
| author | Ali, Mustafa |
| author_facet | Ali, Mustafa |
| author_role | author |
| dc.contributor.none.fl_str_mv | Barlas, Gerassimos El Fakih, Khaled |
| dc.creator.none.fl_str_mv | Ali, Mustafa |
| dc.date.none.fl_str_mv | 2015-05-19T05:43:03Z 2015-05-19T05:43:03Z 2015-02 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 35.232-2015.12 http://hdl.handle.net/11073/7788 |
| dc.language.none.fl_str_mv | en_US |
| dc.subject.none.fl_str_mv | Conformance Testing Adaptive Distinguishing Experiments Parallel Algorithms for Distinguishing Experiments Sequential machine theory Parallel algorithms |
| dc.title.none.fl_str_mv | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| dc.type.none.fl_str_mv | info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/doctoralThesis |
| description | A Master of Science thesis in Computer Engineering by Mustafa Ali entitled, "Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines," submitted in February 2015. Thesis advisor is Dr. Gerassimos Barlas and thesis co-advisor is Dr. Khaled El-Fakih. Soft and hard copy available. |
| format | doctoralThesis |
| id | aus_e5751be1f8eaa892844ae59dad905ba8 |
| identifier_str_mv | 35.232-2015.12 |
| language_invalid_str_mv | en_US |
| network_acronym_str | aus |
| network_name_str | aus |
| oai_identifier_str | oai:repository.aus.edu:11073/7788 |
| publishDate | 2015 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Parallel Algorithms for Distinguishing Nondeterministic Finite State MachinesAli, MustafaConformance TestingAdaptive Distinguishing ExperimentsParallel Algorithms for Distinguishing ExperimentsSequential machine theoryParallel algorithmsA Master of Science thesis in Computer Engineering by Mustafa Ali entitled, "Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines," submitted in February 2015. Thesis advisor is Dr. Gerassimos Barlas and thesis co-advisor is Dr. Khaled El-Fakih. Soft and hard copy available.Many methods are used for the development of experiments and conformance tests based on the specification given in the form Finite State Machines (FSMs). In FSM-based testing, we have an FSM or a black-box Implementation Under Test (IUT) about which we lack some information, and we want to deduce this information by conducting experiments on the IUT. An experiment consists of applying input sequences, observing corresponding output responses, and drawing conclusions about the IUT. An experiment is adaptive if at each step of the experiment the next input is selected which is based on the previously observed outputs. A distinguishing experiment determines the initial state of the FSM. In this thesis, we consider two implementations of an existing sequential algorithm for deriving the minimal length of an adaptive distinguishing experiment for a nondeterministic FSM. We show that the execution time for both of these implementations grows exponentially as the size or the number of transitions of the FSM increases. Accordingly, in order to obtain a solution in a reasonable time, we develop four parallel implementations of the considered sequential algorithms, namely, a multi-core implementation on Central Processing Unit, two Graphical Processing Unit (GPU) implementations based on the platforms like CUDA and Thrust, respectively, and an implementation on a Network of Workstations (NoWs). Comprehensive experiments are conducted to assess and compare the performance and the speedup of the developed implementations. Based on the results obtained from these experiments, the parallel implementation on a NoW provides the best performance and speedup, followed by the CUDA, then the Thrust, followed by the multi-core CPU implementation.College of EngineeringDepartment of Computer Science and EngineeringMaster of Science in Computer Engineering (MSCoE)Barlas, GerassimosEl Fakih, Khaled2015-05-19T05:43:03Z2015-05-19T05:43:03Z2015-02info:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/doctoralThesisapplication/pdf35.232-2015.12http://hdl.handle.net/11073/7788en_USoai:repository.aus.edu:11073/77882025-06-26T12:27:17Z |
| spellingShingle | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines Ali, Mustafa Conformance Testing Adaptive Distinguishing Experiments Parallel Algorithms for Distinguishing Experiments Sequential machine theory Parallel algorithms |
| status_str | publishedVersion |
| title | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| title_full | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| title_fullStr | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| title_full_unstemmed | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| title_short | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| title_sort | Parallel Algorithms for Distinguishing Nondeterministic Finite State Machines |
| topic | Conformance Testing Adaptive Distinguishing Experiments Parallel Algorithms for Distinguishing Experiments Sequential machine theory Parallel algorithms |
| url | http://hdl.handle.net/11073/7788 |