An Efficient Parallel Algorithm for Latin Square Design: A Multi Core CPU Approach
Abstract— The theory of Latin squares is very important tool in design theory. Like much of design theory, Latin squares have various applications in statistics, finite geometries and experimental design, to name a few. In this paper, we proposed an efficient parallel algorithm for Latin square design which have desirable properties for parallel array access. These squares provide conflict free access to various subsets of an n x n array using n memory modules. A transversal of such a square is a set of n entries such that no two entries share the same row, column or symbol. We present a general construction method for building parallel Latin square of order n2for all n.
The proposed algorithm presents a quick parallel method to produce a Latin square design and a parallel conflict access of data in SIMD system. The simulation results of the proposed parallel algorithm for Latin square design were compared with the traditional sequential algorithm Latin square design in terms of speedup and efficiency. The results of parallel Latin Square design were very promising and showed a potential that this design could successfully be applied to the parallel routing problems for conflict free data access. At last, the results show that the parallel versions of former sequential algorithm with simple modifications achieve the super linear speedup up to 200 times for matrix size of 256.
Index Terms: Latin square, multi core processor, parallel processing, simulation, parallel memory system, skewing scheme, multistage interconnection network.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Copyright & License
All Research Plus Journals (RPJ) publish open access articles under the terms of the Creative Commons Attribution (CC BY-SA 4.0) https://creativecommons.org/licenses/by-sa/4.0/ License which permits use, distribution and reproduction in any medium, provided the original work is properly cited & ShareAlike terms followed.
Copyright on any research article in a journal published by a RPJ is retained by the author(s). Authors grant RPJ a license to publish the article and identify itself as the original publisher. Upon author(s) by giving permission to RPJ either via RPJ journal portal or other channel to publish their research work in RPJ agrees to all the terms and conditions of https://creativecommons.org/licenses/by-sa/4.0/ License and terms & condition set by RPJ.
3rd party copyright: It is the responsibility of author(s) to secure all necessary copyright permissions for the use of 3rd-party materials in their manuscript.
Research Plus Journals Open Access articles posted to repositories or websites are without warranty from RPJ of any kind, either express or implied, including, but not limited to, warranties of merchantability, fitness for a particular purpose, or non-infringement. To the fullest extent permitted by law RPJ disclaims all liability for any loss or damage arising out of, or in connection, with the use of or inability to use the content.