Abstract:

Sequential computation assumes the existence of one processing unit while parallel computation exploits the cumulative power of multiple processing units. We, as humans, are mostly familiar with sequential computation since we usually complete tasks using a single natural "processor", i.e., our brain. However, parallel processing continuously takes place both on individual and social level as well as in natural, industrial and digital environments like for example weather formation, car manufacturing or a modern smartphone, respectively. Sorting, i.e., the process of putting discrete entities in a particular order, is a task performed extremely frequently and inherently contains parallelism in the sense that entities to be sorted can be partitioned in smaller sets which are then addressed simultaneously. Moreover, in the relevant literature as well as in the context of university courses on Parallel Algorithms, sorting algorithms, i.e., methods exploiting multiple processing units for putting entities in a particular order, have been highly addressed. Focusing on educational and training aspects, for students who begin to study parallel algorithms visualization is extremely helpful, even if not always trivially obtained.

In this work, we designed and implemented a web application for the visualization of two well-studied parallel sorting algorithms for two-dimensional meshes, namely the Shearsort parallel sorting algorithm and the parallel sorting algorithm by Schnorr and Shamir, which is optimal for two-dimensional meshes. These two parallel algorithms, apart from their apparent technical/practical value, are in the standard set of parallel algorithms studied in respective university-level courses. Based also on personal experience, our work has been motivated by our wish to provide a simple and attractive yet useful online tool to students where they can experiment with the Shearsort and the Schnorr-Shamir parallel sorting algorithms on two-dimensional meshes via a graphical and interactive environment. In this way, students can have a real visible experience regarding the behaviour of abstract methods and, in addition, they can actively participate in the formation of this experience, thus gaining a deeper understanding of parallel computation, parallel techniques and their practical impact. Our game-like application enables users to define and fill their own two-dimensional mesh, either automatically or manually, and then execute either Shearsort of Schnorr-Shamir parallel sorting algorithm. The mesh can be visually observed during each step of the algorithms as well as in its final sorted form after the completion of the selected algorithm. Moreover, users can navigate in the sequence of executed steps after the completion of the execution of each algorithm, also receiving additional information on the particular tasks implemented during each step. Using the application does not require advanced technical skill or sophisticated equipment. To the best of our knowledge, no other similar application is available while there are indeed few java implementations available in source-code format (e.g., github), which, however, do not really correspond to parallel implementations. Regarding implementation, the challenging and innovative nature of our application lies in the use of Javascript, React.js in particular, for building a truly parallel execution environment for Shearsort and the Schnorr-Shamir parallel sorting algorithms.

Keywords:

Web app, parallel sorting on 2D meshes, visualization, graphical and interactive training environment, parallel algorithms, Shearsort, Schnorr-Shamir.