A HYPERBOLIC MODEL FOR COMMUNICATION IN LAYERED PARALLEL-PROCESSING ENVIRONMENTS

We introduce a model for communication costs in parallel processing en vironments, called the hyperbolic model, which generalizes two-paramet er dedicated-link models in an analytically simple way. The communicat ion system is modeled as a directed communication graph in which termi nal nodes represent the application processes and internal nodes, call ed communication blocks (CBs), reflect the layered structure of the un derlying communication architecture. A CB is characterized by a two-pa rameter hyperbolic function of the message size that represents the se rvice time needed for processing the message. Rules are given for redu cing a communication graph consisting of many CBs to an equivalent two -parameter form, while maintaining a good approximation for the servic e time. We demonstrate a tight fit of the estimates of the cost of com munication based on the model with actual measurements of the communic ation and synchronization time between end processes. We compare the h yperbolic model with other two-parameter model and, in appropriate lim its, show its compatibility with the LogP model. (C) 1996 Academic Pre ss, Inc.