SUMMARY In this paper, we study CPU utilization time patterns of several MapReduce applications. After extracting running patterns of several applications, the patterns along with their statistical information are saved in a reference database to be later used to tweak system parameters to efficiently execute future unknown applications. To achieve this goal, CPU utilization patterns of new applications along with its statistical information are compared with the already known ones in the reference database to find/predict their most probable execution patterns. Because of different pattern lengths, dynamic time warping (DTW) is utilized for such comparison; a statistical analysis is then applied to DTWs' outcomes to select the most suitable candidates. Furthermore, under a hypothesis, we also proposed another algorithm to classify applications under similar CPU utilization patterns. Finally, dependency between minimum distance/maximum similarity of applications and scalability (in both input size and number of virtual nodes) is studied. Here, we used widely used applications (WordCount, Distributed Grep, and Terasort) as well as an Exim MainLog parsing application to evaluate our hypothesis in automatic tweaking MapReduce configuration parameters in executing similar applications scalable on both size of input data and number of virtual nodes. Results are very promising and showed the effectiveness of our approach on a private cloud with up to 25 virtual nodes. Concurrency and Computation: Practice and Experience, 2012. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, we study the dependency between MapReduce configuration parameters and network load of fixed-size MapReduce jobs during the shuffle phase, then we propose an analytical method to model this dependency. Our approach consists of three key phases: profiling, modeling, and prediction. In the first stage, an application is run several times with different sets of MapReduce configuration parameters (here number of map tasks and number of reduce tasks) to profile the network load of an application in the shuffle phase on a given cluster. Then, the relation between these parameters and the network load is modeled by multivariate linear regression. For evaluation, three applications (Word Count, Exim Main log parsing, and TeraSort) are utilized to evaluate our technique on a 5-node MapReduce private cluster.

In this paper, a diverse range of routing algorithms is classified into a new family of routings called zone-ordered label-based routing algorithms. The proposed classification is based on three common steps (factors) for generating such routings, namely, graph labeling, deadlock-free zones, and zone ordering. The main goal of this classification is to define several new routing concepts and streamline the knowledge on routing algorithms. Following the classification, a novel methodology is proposed to generate routing algorithms for irregular networks. The methodology uses the three mentioned steps to generate deadlock-free routings. Consequently, the methodology-based routings fall into the category of zone-ordered label-based routings. However, the graph labeling method (first step) used in the methodology is based on multiple spanning tree construction on the network. The simulation results show that constructing further spanning trees may result in routing algorithm with better performance.

Irregular networks provide more scalability and better cost-performance for network-based parallel computing systems. There has been much work done on developing routing algorithms for this class of networks. In this paper, a general methodology for generating deadlock-free routing algorithms for irregular networks is proposed. It not only introduces three novel efficient routing algorithms, but also covers the three best-known routing algorithms already proposed for irregular networks in the literature, namely up/down, left/right, and L-turn routing algorithms. As revealed by simulation results, the performance of the six routing algorithms mainly depends on network topology and different scenarios some of proposed routing algorithms exhibit superior performance.

So far, many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube,torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the a forementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.

Recent studies have revealed that on-chip interconnects neither is wire plentiful nor is bandwidth cheap. Based on the results of these studies, in physical design of multiprocessor system-on-chip (MPSoCs), both the wiring density constraint and routing of wires are controversial issues, and there is a trade-off between the network bandwidth and wiring limitations. Therefore, in this paper, we introduce a new topology, named mesh connected crossbars (MCC), to enhance the communication bandwidth between processing elements; the proposed topology, also, has significant topological advantages over traditional torus- and mesh-based NoCs. Furthermore, we study the topological properties of MCCs and propose deterministic and fully adaptive deadlock-free routing algorithms in an attempt to evaluate the performance of MCC in different working conditions. The simulation results show that under constant wiring conditions, MCC exhibits higher performance and consumes lower energy in comparison with equivalent torus or mesh networks.

In this paper, we propose the first comprehensive mathematical performance model for product networks where fully adaptive routing is applied. Besides the generality of this model which makes it suitable to be used for any product graph, our analysis shows that the proposed model exhibits high accuracy. Simulation results show the validity and accuracy of the model even in heavy traffic and saturation region, where other models have severe problems for prediction.