- 21 -

or distributed systems (e.g. [NoTh93] and other references below). The general representation of this problem is that of a static program graph consisting of modules interconnected via links, where modules serve to perform various processing tasks and links indicate required intermodule communication. Both modules and links are labelled with figures indicating load or cost properties.

A multiprocessor or distributed system graph is used to describe possible computation sites for program modules. Nodes and links of this graph are labelled with resource constraints limiting node processing or communication capabilities. The goal is to find a program partitioning and mapping on the system graph without violating any of the given constraints and minimizing overall cost. This problem formulation seems similar to the one considered in this paper. However, important differences and mismatches exist.

First, most suggested approaches consider specific resource load types (and constraints) only. In fact, a large group does not consider load constraints at all, but aims solely at finding a graph mapping with minimum cost ([KLZ97], [LeSh97], [BiEl95], [Bill94], [LLK92], [Fern89], [Lo88], [Tows86], [Ston77]). A second group considers for each program module a (CPU) processing load figure and aims at a mapping implying a balanced load on each processor ([OlMa95], [IqBo95], [HaLi92], [NiHa91], [Bokh88]). Further load types (e.g. memory, communication loads) are not considered. Other approaches extend the model by considering cost in addition ([SBAM96]), [YaSa93], [BNA92], [KiPa90], [Efe82]).

A few approaches have been described taking into account many resource constraints given in a particular mapping problem context. In [YWPS95] the mapping problem is considered taking into account (among others) CPU load, memory load and communication bandwidth. However, the approach employs branch-and-bound and simulated annealing techniques, both of which have exponential worst-case complexity. Similarly, in [MLT82] an approach based on branch-and-bound techniques is described. The approach presented in ([WoMo93]) has polynomial time complexity and takes both a processing and a shared bus communication load into account. However, it does not consider more endsystem load types (e.g. memory, network I/O).

A second important aspect concerns the cut-oriented description of the multimedia allocation problem. Here, each cut is associated with load figures, not each module. This description allows to take into account for each cut both the processing load(-tuple) implied by allocated components and the load(-tuple) implied by the remote communication at a specific chain cut

Seite 21: vorherige Seite | nächste Seite | Übersicht

- 22 -

(see Section 3). This allows to take into account the endsystem load required for remote communication which can be very significant, given that compression/decompression may be provided. Using cut descriptions for solving the problem is accurate. Almost all existing approaches consider endsystem load as being not influenced by communication requirements (i.e. communication implies load within the network only). The approach in [WoMo93] does a first step in this direction. However, it simplifies the relationship by interpreting required communicaton load twofold: as network bandwidth requirement and as a processing load requirement which has to be added to a processor's workload. In general (and especially when compression/ decompression is done), this simplification does not hold.

Finally, existing approaches imply a higher computation complexity than our approach. One reason is that many of them were designed for other, in some respect more general, mapping problems (e.g. for instance for arbitrary program graph shapes). Another reason is the method used. The approach in [SBAM96] was specifically designed to achieve a low computational complexity, which is also lower than our protocol's. However, when applied to the host/satellite problem, the method is basically equivalent to the initialisation part of the SQ algorithm, which (as a stand-alone solution) delivers significantly worse solutions.1 This also shows that solutions exhibiting good average behaviour in general settings (as indicated in [SBAM96]), can prove inferior to specialized solutions when applied to special cases.

In summary, none of the existing approaches can be considered as fully applicable to the mapping problem considered in this paper. In constrast, our approach directly targets the requirements of the multimedia host-satellite allocation problem including independence of the number of load types considered, cut-oriented load considerations and computation efficiency.

5 Summary and Future Work

Many multimedia applications require intermediate processing between media sources and sinks. In order to support such applications computers are being designed relieving end-user terminals from heavy processing load. In this paper, the problem of allocating intermediate processing components on such computers was studied. The problem was formulated for common structures occuring in multimedia application settings, namely star-shaped application graphs and host-satellite distributed computer settings.

1. Also, the approach does not consider all required load types and is also not cut-oriented in the sense decribed above.

Seite 22: vorherige Seite | nächste Seite | Übersicht

- 23 -

The allocation problem was formulated in terms of chain cuts taking into account both processing and communication load requirements. Several approaches for determining optimized cuts have been considered including an approximation scheme and several fast heuristics. All of these are capable to take into account as many load constraints as required. Performance measurements showed the efficiency of the SQ algorithm delivering chain cut solutions very close to the optimum, while requiring less time than other approaches, both in comparison with an optimal scheme which was used for benchmarking and an approach designed for the related multiple-choice multiple-knapsack problem.

Though designed for the described host-satellite problem, the SQ algorithm is applicable to more general cases as well. It is easy to see that SQ is applicable without modifications to the case of several star-shaped graphs using the same host. In addition, with minor modifications, SQ can be used for sets of star-shaped and linear graphs traversing the same host. Currently, we investige settings where sets of graphs are allocated using several of a set of potential hosts.

Along another line, we look at an integrated way to couple QoS calculations and determining component distribution. Finally, we design a protocol for gathering required QoS and allocation information and performing resource reservation in accordance to calculated QoS and mapping decisions.

References

[AMZ95] E. Amir, S. McCanne, H. Zhang. An Application Video Level Gateway. 3rd ACM Int. Multimedia Conference, San Francisco, Nov. 1995.

[BeSt97] R. Bertram, R. Steinmetz. Scalability of Audio Quality for Networked Multimedia Environments. IEEE Int. Conference on Multimedia Computing and Systems, Ottawa, June 1997.

[BiEl95] A. Billionnet, S. Elloumi. An Algorithm for Finding the k-best Allocations of a Tree Structured Program. Journal of Parallel and Distributed Computing, 26, pp/ 225-232, 1995.

[Bill94] A. Billionnet. Allocating Tree Structured Programs in a Distributed System with Uniform Communication Costs. IEEE Trans. on Parallel and Distributed Systems, Vol. 5, No. 4, Apr 1994.

[BLMS96] H. Bryhni, H. Lovett, E. Maartmann-Moe, D. Solvoll, T. Sorenson. On-Demand Regional Television over the Internet. 4th ACM Int. Multimedia Conference, Boston, Nov. 1996.

[Bokh88] Partitioning Problems in Parallel, Pipelined, and Distributed Computing. IEEE Transactions on Computers, Vol. 37, No. 1, pp 48-57, Jan 1988.

[BNG92] N.S. Bowen, C.N. Nikolau, A. Ghafoor. On the Assignment Problem of Arbitrary

Seite 23: vorherige Seite | nächste Seite | Übersicht

- 24 -

Process Systems to Heterogeneous Distributed Computer Systems. IEEE Trans. on Computers, Vol. 41, No. 3, pp. 257-273, 1992.

[DFR96] G. Dermler, W. Fiederer, I. Barth, K. Rothermel. A Negotiation and Resource Reservation Protocol (NRP) for Distributed Multimedia Applications. IEEE Int. Conference on Multimedia Computing and Systems, Hroshima, Japan, June 1996.

[DFR97] G. Dermler, W. Fiederer, K. Rothermel. QoS Negotiation and Resource Reservation for Distributed Multimedia Applications. IEEE Int. Conference on Multimedia Computing and Systems, Ottawa, June 1997.

[DGOR94] G. Dermler, T. Gutekunst, F. Ruge, E. Ostrowski. Sharing Audio/Video Applications among Heterogeneous Platforms. 5th IEEE COMSOC Int. Workshop on Multimedia Communications, Kyoto, Japan, 1994.

[DVV94] D. Deloddere, W. Verbiest, H. Verhille. Interactive Video on Demand. IEEE Communications, Vol. 32, No. 5, pp. 82-88, May 1994.

[Efe82] K. Efe. Heuristic Models of Task Assignment Scheduling in Distributed Systems. IEEE Computer, pp. 50-56, June 1982.

[Fern89] D. Fernandez-Baca. Allocating Modules to Processors in a Distributed System. IEEE Trans. on Software Engineering, Vol. 15, No. 11, Nov 1989.

[GaJo79] M. R. Garey, D.S. Johnson. Computers and Intractability- A Guide to the Theory of NP-Completeness, Freeman, California, USA, 1979.

[IMA93] HP Company, IBM Corp., SunSoft Inc. Multimedia System Services, Version 1.0, available via ftp from ibminet.awdpa.ibm.com.

[HaLi92] P. Hansen, K.W. Lih. Improved Algorithms for Partitioning Problems in Parallel, Pipelined and Distributed Computing. IEEE Trans. on Computers, Vol. 41, No. 6, pp. 769- 771, June 1992.

[HaSm96] J. Han, B. Smith. CU-SeeME VR Immersive Desktop Teleconferencing. 4th ACM Int. Multimedia Conference, Boston, Nov. 1996.

[Iqbl91] M.A. Iqbal. Approximate Algorithms for Partitioning Problems, International Journal of Parallel Programming, October 1991.

[IqSh93] M.A. Iqbal, M.E. Shaaban. Heterogeneous Partitioning of Chain Structured Image Processing Tasks, IEEE Workshop on Computer Architectures for Machine Perception (CAMP'93), December 1993.

[IqBo95] M.A. Iqbal, S.H. Bokhari. Efficient Algorithms for a Class of Partitioning Problems, IEEE Trans. Parallel & Distributed Systems, vol.6, no. 2, February 1995.

[KiPa90] C.H. Lee, M. Kim, C.I. Park. An Efficient K-Way Graph Partitioning Algorithm for Task Allocation in Parallel Computing Systems. IEEE Computer, pp. 748-751, 1990.

[KKKM95]P.H. Kelly, A. Katkere, D.Y. Kuramura, S. Moezzi, S. Chtterjee, R. Jain. An architecture for multiple perspective interactive video. 3rd ACM Int. Multimedia Conference, Boston, San Francisco, Nov 1995.

[LeSh97] C.H. Lee, K.G. Shin. Optimal Task Assignment in Homogeneous Networks. IEEE Trans. on Parallel and Distributed Systems, Vol. 8, No. 2, Feb 1997.

Seite 24: vorherige Seite | nächste Seite | Übersicht

- 25 -

[Lo88] V.M. Lo. Heuristic Algorithms for Task Assignment in Distributed Systems. IEEE Trans. on Computers, Vol. 37, No. 11, pp. 1384-1397, Nov 1988.

[KLZ97] Y. Kopidakis, M. Lamari, V. Zissimopoulos. On the Task Assignment Problem: Two New Efficient Heuristic Algorithms. Journal of Parallel and Distributed Computing, Vol. 42, pp. 21-29, 1997.

[LLK92] C.H. Lee, D. Lee, M. Kim. Optimal Task Assignment in Linear Array Networks. IEEE Trans. on Computers, Vol. 41, No. 7, pp. 877-880, July 1992.

[MAHT97] K. Minami, A. Akutsu, H. Hamada, Y. Tonomura. Enhanced Video Handling based on Audio Analysis. IEEE Int. Conference on Multimedia Computing and Systems, Ottawa, June 1997.

[MLT82] P.R. Ma, E.Y.S. Lee, M. Tsuchiya. A Task Allocation Model for Distributed Computing Systems. IEEE Trans. on Computers, Vol. 31, No. 1, Jan 1982.

[Mose96] M. Moser. Declarative Scheduling for Optimally Graceful QoS Degradation. IEEE Int. Conference on Multimedia Computing and Systems, Hiroshima, Japan, June 1996.

[MXBX96]Z. Maojun, H. Xiaofeng, Y. Bing, K. Xishu. Fats Algorithms for Compositing Multi-Way Compressed Video. IEEE Int. Conference on Multimedia Computing and Systems, Hiroshima, Japan, June 1996.

[NaSm95] Klara Nahrstedt, Jonathan Smith. The QoS Broker. IEEE Multimedia, Vol. 2, No. 1, pp. 53-67, Spring 1995.

[NiHa91] D.M. Nicol, D.R. O'Hallaron. Improved Algorithms for Mapping Pipelined and Parallel Computations. IEEE Trans. on Computers, Vol. 40, No. 3, pp. 295-305, Mar 1991.

[NoTh93] M.G. Norman, P. Thanisch. Models of Machines and Computation for Mapping in Multicomputers. ACM Computing Surveys, Vol. 25, No. 3, Sep. 1993.

[OlMa95] B. Olstad, F. Manne. Efficient Partitioning of Sequences. IEEE Trans. on Computers, Vol. 44, No. 11, pp. 1322-1326, Nov 1995.

[RBH94] K. Rothermel, I. Barth, T. Helbig. CINEMA - An Architecture for Distributed Multimedia Applications. Architecture and Protocols for High-Speed Networks, pp. 253-271, Kluwer Academic Publishers, 1994.

[SBAM96] A.D. Stoyenko, J. Bosch, M. Aksit, T.J. Marlowe. Load Balanced Mapping of Distributed Objects to Minimize Network Communication, Journal of Parallel and Distributed Computing 34, pp. 117-136, 1996.

[ShSe95] B. Shen, I.K. Sethi. Inner-Block Operations on Compressed Images. 3rd ACM Int. Multimedia Conference, San Francisco, Nov 1995.

[SMK96] L.C. de Silva, T. Miyasato, F. Kishino. Emotion Enhanced Multimedia Meetings Using the Concept of Virtual Space Teleconferencing. IEEE Int. Conference on Multimedia Computing and Systems, Hiroshima, Japan, June 1996.

[Sren96] C.J. Sreenan. Resource Management System for a Broadband Multipoint Bridge. IEEE Int. Conference on Multimedia Computing and Systems, Hiroshima, Japan, June 1996.

[SSJH96] F. Samaria, H. Syfrig, A. Jones, A. Hopper. Enhancing Network Services through Multimedia Data Analysers. 4th ACM Int. Multimedia Conference, Boston, Nov. 1996.

Seite 25: vorherige Seite | nächste Seite | Übersicht

- 26 -

[StNa95] R. Steinmetz, K. Nahrstedt. Multimedia: Computing, Communications and Applications. Prentice Hall, Innovative Technology Series, 1995.

[Ston77] H.S. Stone. Multiprocessor Scheduling with the Aid of Network Flow Algorithms. IEEE Trans. on Software Engineering, Vol. 3, No. 1, Jan 1997.

[Tows86] D. Towsley. Allocating Programs Containing Branches and Loops Within a Multiple Processor System. IEEE Trans. on Software Engineering, Vol. 12, No. 10, pp. 1018- 1024, Oct 1986.

[VKBG95] Andreas Vogel, Brigitte Kerherve, Gregor von Bochmann and Jan Gecsei. Distributed Multimedia and QOS: A Survey. IEEE Multimedia, Summer 1995, pp. 10-18.

[Wo96] Lars Wolf. Resource Management for Distributed Multimedia Systems. Kluwer Academic Publisher, Boston/Dordrecht/London 1996.

[WoMo93] C.M. Woodside, G.G. Monforton. Fast Allocation of Processes in Distributed and Parallel Systems. IEEE Trans. on Parallel and Distributed Systems, Vol. 4, No. 2, Feb 1993.

[YMGH96] N. Yeadon, A. Mauthe, F. Garcia, D. Hutchison. QoS Filters: Addressing the Heterogeneity Gap. European Workshop on Interactive Distributed Multimedia Systems and Services, Berlin, Germany, March 1996.

[Zhan93] L. Zhang et al. RSVP: A New Resource Reservation Protocol. IEEE Netowrks Magazine, pp. 8-18, Sep 1993.

[YaSa93] S.S. Yau, V.R. Satish. A Task Allocation Algorithm for Distributed Computing Systems. IEEE Computer, pp. 336-342, 1993.

[YWPS95] S. Yalamanchili, L.T. Winkel, D. Perschbacher, B. Shenoy. Partitioning and Mapping in Embedded Multiprocessor Architectures in the Presence of Constraints. Concurrency: Practice and Experience, Vol. 7(3), pp. 167-189, May 1995.

Seite 26: vorherige Seite | Übersicht