\documentstyle[times,epsf,acmproc]{article} \setlength{\textheight}{9in} \setlength{\columnsep}{1.8pc} \setlength{\textwidth}{6.8in} \setlength{\footheight}{0.0in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in} \setlength{\oddsidemargin}{-.19in} \setlength{\parindent}{1pc} \title{Characterizing the Network Behavior \\ of Parallel Programs on Ethernet\\ \bf Proposal} \author{ P. Dinda \hspace{.5in } B. Garcia \hspace{.5in} K. Leung \\ Carnegie-Mellon University} \begin{document} \input{psfig} \maketitle \section{Introduction} We propose to characterize the network behavior of message passing parallel programs running on Ethernet. Many parallel programs, especially those that follow the popular SPMD model, exhibit global communication behavior that can be classified into a small number of patterns. We will create parallel applications that exhibit each of these communication patterns and measure their network characteristics. From these measurements, we will derive models that can produce traffic that exhibits these characteristics. To see if the models are composible, we will measure two complex parallel applications which exhibit several of the communication patterns. \section{Motivation} Local area computer networks are starting to be used as communication systems for parallel computing. As the link and aggregate bandwidths of LANs approach those of commercial parallel supercomputers, porting serious parallel programs to run on clusters of workstations is becoming increasingly attractive. Overwhelmingly, the performance of a parallel program on a distributed memory system is limited by the performance of message passing. In commercial parallel supercomputers, the message passing system provides a send/receive interface to communicate data between nodes over a special purpose interconnection network. In a workstation cluster, a send/receive interface such as PVM~\cite{Sund90} is layered on top of the general purpose protocol stack which communicates via a general purpose network. LANs and TCP/IP have been designed using network traffic studies that emphasize single node interactive and bulk transfer applications. Since parallel application traffic will grow as LANs become faster, it is important for LAN and protocol designers to understand the characteristics of this traffic so that it can be supported with high performance and minimal impact on other traffic. \section{Communication Patterns} \label{sec:commpats} A popular model for programming parallel computers is the Single Program, Multiple Data (SPMD) model. In the SPMD model, each processor executes the same program, which works on processor-local data. Frequently, the processors exchange data by message passing, which also synchronizes the processors. This message exchange is referred to as a {\em communication phase}. The parallel program executes as interleaved communication and local computation phases. A communication phase can be classified according to the pattern of message exchange among the processors. For example, a phase may exhibit a {\em neighbor} pattern, where each processor $p_i$ sends to processors $p_{i-1}$ and $p_{i+1}$. Another common pattern is {\em all-to-all}, where each processor sends to every other processor. A third pattern is {\em partition}, where the processors are partitioned into two or more sets and each member of a set sends to every member of another set. Fourth, a single processor may {\em broadcast} a message to every other processor. Finally, the pattern can be a {\em tree}, where every second processor sends to its left neighbor and then drops out. This is repeated until one processor remains. Sometimes this is followed with a ``down-sweep'', reversing the process. These communication patterns are summarized in Figure~\ref{fig:commpats}. \begin{figure} \centerline{\epsfxsize=2.5in \epsfbox{commpatterns.eps}} \caption{SPMD Communication patterns} \label{fig:commpats} \end{figure} \begin{figure} \label{fig:measuredapps} \centering \begin{tabular}{|l|l|} \hline Pattern & Measured Application \\ \hline Neighbor & SOR \\ All-to-all & 2DFFT \\ Partition & Tasking 2DFFT \\ Broadcast & Sequential I/O \\ Tree & Histogram \\ \hline \end{tabular} \caption{Representative Applications} \end{figure} \section{Measurement and Modeling} \label{sec:measure} The network traffic generated by each of the communications patterns described in Section \ref{sec:commpats}. will be measured separately. For each of patterns described, we will measure a representative application, as shown in Figure~\ref{fig:measuredapps}. For each representative application, we will monitor the network traffic on the Ethernet segment that connects the group of workstations running the application, and gather packets using \verb"tcpdump" (which collects packets on the Ethernet for retrospective analysis of the traffic.) We are interested in studying the network throughput, the packet inter-arrival rate, the network delay, and the ``burstiness'' of the traffic as generated by the parallel applications we are interested in studying. In addition to the statistical characteristics of each of these values, we also want to understand their time and frequency domain behavior. Our measurements have two purposes. First, we want to compare and contrast parallel application traffic with traditional single node interactive and bulk transfer (\verb"telnet" and \verb"ftp") traffic, which has been well studied by researchers~\cite{Guss90,LeWi91,LTWW93}. This should provide some insight into how to design networks suitable for parallel applications. Secondly, we want to produce a model for each communication pattern that can produce network traffic corresponding to that pattern. \section{Real Applications} \begin{figure} \label{fig:realapps} \centering \begin{tabular}{|l|c|c|} \hline Pattern & Diagnosis & Airshed \\ \hline Neighbor & X & X \\ All-to-all & & X \\ Partition & & Possible\\ Broadcast & Possible & X \\ Tree & X & Possible \\ \hline \end{tabular} \caption{Communication Patterns of Real Applications} \end{figure} Once we have models for each communication pattern, we want to determine if they can be composed to characterize the traffic of large parallel programs that exhibit many different communication patterns. To do so, we will measure the network characteristics described in Section \ref{sec:measure} to two ``real'' parallel applications, which exhibit multiple communication patterns as shown in Figure~\ref{fig:realapps}. The applications are distributed system-level diagnosis, and air quality modeling. \subsection{Distributed System-level Diagnosis} One of the benefits of parallel and distributed programs is the ability to operate successfully even if some processors are faulty. If a process is spawned on a new processor which becomes faulty during the computation, then the other processors in the system should be able to recognize this. In response, they can re--spawn the process onto a good node. In this way, faults within a distributed computing environment can be masked to the end user. Of course, the problem then becomes --- how can one tell if a processor is faulty? This application is an attempt to provide a solution to this need. It allows each of the processors in a distributed system to run tests on other processors and to diagnose the state of every processor in the system. It is based on the algorithm described in \cite{Bian92}. The current implementation of this algorithm has neighbor and broadcast communication. Further, other communication patterns may be exploitable to reduce diagnosis latency, the number of messages, and message length. It will be interesting to see how much of a benefit each of these enhancing techniques actually provides. \subsection{Air Quality Modeling} The air quality modeling application~\cite{Kum94} simulates the movement of emitted chemicals in the atmosphere given emmission concentrations and locations, and wind vectors. This large application is currently being parallelized here at CMU~\cite{Din94} to run on a variety of parallel computing platforms. The application, called ``Airshed'' exhibits a variety of communication patterns. \section{Requirements and Plan} We will need a quiescent set of workstations and an Ethernet segment that we can monopolize for short periods of time. Additionally, one workstation on this segment must have a packet filter device driver and allow us root access so we can operate the network interface in promiscuous mode. We intend to have the measurement of the representative applications completed by the progress report date. If we get the measurement tools up and running early, we will also measure the real applications by that point. \begin{thebibliography}{Din94} \bibitem[1]{Bian92} Bianchini, R., Buskens, R., ``Implementation of On-Line Distributed System-Level Diagnosis Theory,'' {\em IEEE Transactions on Computers}, Vol. 41, No. 5, May 1992. \bibitem[2]{Din94} Dinda,P., Gross, T., O'Hallaron, D., Segall, E., Stichnoth, J., Subhlok, J., Webb, J., and Yang, B., ``The CMU task parallel program suite,'' Technical Report CMU-CS-94-131, School of Computer Science, Carnegie Mellon University, March, 1994. \bibitem[3]{Guss90} Gussella, R., ``A Measurement Study of diskless workstation traffic on an ethernet,'' {\em IEEE Transactions on Communications}, pp. 1557-1568, Sep. 1990. \bibitem[4]{Kum94} Kumar, N., Odman M.T.,and Russell,A.G., ``Multiscale air quality modeling: application to southern california,'' {\em Journal of Geophysical Research}, 99:5385-5397, 1994. \bibitem[5]{LTWW93} Leland, W.E., Taqqu, M.S., Willinger, W., and Wilson, D.V., ``On the Self-Similar Nature of Ethernet Traffic,'' {\em Proceedings of ACM SIGCOMM}, pp. 183-193, 1993. \bibitem[6]{LeWi91} Leland, W.E. and Wilson,D.V., ``High time-resolution measurement and analysis of LAN traffic: implications for LAN interconnections,'' {\em Proceedings of IEEE INFOCOM}, pp. 1360-1366, 1991. \bibitem[7]{Sund90} Sunderam, V.S., ``PVM: A framework for parallel distributed computing,'' {\em Concurrency: Practice and Experience 2}, 4 (Decemeber 1990), pp. 315-339. \end{thebibliography} \end{document}