Graph partitioning into multiple components such that the number of edges removed from each component is minimal

Parallel processing is referred to as simultaneous execution of a program (which is split into smaller components) on multiple processors in order to achieve faster speed than the serial mode. The main idea, the process of solving an issue can usually be subdivided into smaller subunits, which can be solved simultaneously by executing these subunits and coordinating them in the shortest possible time.Parallel programming was created to make the best use of system resources and to increase the speed and efficiency of the program on the processors. In this kind of programming, parts of the main program that can run concurrently are divided into several sub-programs and run simultaneously on multiple processors. A part of the program that does not run parallel runs serially on a single processor.Here, the main problem is subdivided into tasks and the interactions between tasks are graphically represented. Now, depending on the type of problem, how to divide the graph into components, so that there are at least the number of edges between the divided components, and finally, by mapping tasks to processes, the maximum speed increase compared to the serial run to achieve.In this study, a graph of functions is considered as convertible into a bipartite graph, and then the graph is divided into two components according to the principles of bipartite graph. Finally, each component is mapped to a processor. In this implementation, the Visual Studio software and the C# Programming language have been used. And in the end, according to the law of rescue, the speed of the parallel run is calculated from the serial mode, and is shown in the table.

کلیدواژه ها:

Parallel programming ، speed Up ، Graph partitioning ، bipartite graph