lien@osu-eddie.UUCP (03/08/87)
From: Yao-Nan Lien <lien> Recently, there are many articles discussing the hypercube architecture. Definately, there is a problem of partitioning the problem to be solved into many subtasks and mapping these tasks to the real processors. The major concern is to balance the processor utilization and to minimize the possible communication among processors. There are quite a few reserchers working on this problem. As far as I know, there is no optimal algorithm to solve this problem in reasonable amount of time. Approximate algorithms are needed. Due to the time constraint, only simple algorithm can be used. I am wondering that what is the range of the time constraint in most applications? I was told that the time is limited in a few seconds ( or a few minutes). Is this true? Why can't we use better but slightly slower algorithms to solve it if the program is to be reused again and again? I guess that the existing problems are diversified. Some problems are time critical, but some are not. If there are substantial amount of problems in this category, better but slower algotithms may be worth to develop. -- Yao-Nan Lien
eugene@pioneer.arpa (Eugene Miya N.) (03/09/87)
In article <3312@osu-eddie.UUCP> lien@osu-eddie.UUCP writes: >From: Yao-Nan Lien <lien> > >Definately, there is a problem of partitioning the problem to be >solved into many subtasks and mapping these tasks to the real >processors. The major concern is to balance the processor >utilization and to minimize the possible communication among >processors. >-- Yao-Nan Lien A paper was written some time ago about the general partitioning problem. It's NP-complete. Not trivial. From the Rock of Ages Home for Retired Hackers: --eugene miya NASA Ames Research Center eugene@ames-aurora.ARPA "You trust the `reply' command with all those different mailers out there?" "Send mail, avoid follow-ups. If enough, I'll summarize." {hplabs,hao,ihnp4,decwrl,allegra,tektronix,menlo70}!ames!aurora!eugene
wagner@utcsri.UUCP (Alan Wagner) (03/11/87)
In article <3312@osu-eddie.UUCP> lien@osu-eddie.UUCP writes: >>From: Yao-Nan Lien <lien> >> >>Definately, there is a problem of partitioning the problem to be >>solved into many subtasks and mapping these tasks to the real >>processors. The major concern is to balance the processor >>utilization and to minimize the possible communication among >>processors. >>-- Yao-Nan Lien >A paper was written some time ago about the general partitioning >problem. It's NP-complete. Not trivial. To follow up on Eugene's remarks, trying to map processes to processors so that only neighbour to neighbour communication is required is the subgraph isomorphism problem (NP-complete, see Garey&Johnson) see also S.H. Bokhari, On the Mapping Problem, IEEE Trans. on Computers, C-30, 3 , March 1981. More specifically if we restrict the host to a hypercube (i.e. Determine if a graph is a partial subgraph of hypercube of some dimension n) then the problem remains NP-complete F. Afrati and C. H. Papadimitriou and G. Papageorgiou, The Complexity of Cubical Graphs, Eleventh Intl. Colloquium on Automata, Languages and Programming, 1984, G. Cybenko, D.W. Krumme and K.N. Venkataraman, Hypercube Embedding is NP-complete, Dept. of Computer Science, Tufts University, Medford August 1985 And more recently even when the source graph is a tree (i.e Given a tree T and integer k is T a subgraph of a cube of size k.) the problem is is still NP-complete. A. Wagner and D. Corneil, Embedding Trees in a Hypercube is NP-complete, Tech Report #197/87 University of Toronto, Toronto, Can. With respect to trees, an interesting conjecture concerning binary trees mentioned in S.N. Bhatt, F.R.K. Chung, T.Leighton and A.L. Rosenberg, Optimal Simulations of Tree Machines, Proceedings of the 27th FOCS Symposium, 1985 is that "Are all binary trees with 2^n nodes a subgraph of a cube of size n+1?". Alan Wagner
graham@convex.UUCP (03/11/87)
/* Written 1:59 am Mar 9, 1987 by eugene@pioneer.arpa in convex:comp.arch */ >Definately, there is a problem of partitioning the problem to be >solved into many subtasks and mapping these tasks to the real >processors. The major concern is to balance the processor >utilization and to minimize the possible communication among >processors. >-- Yao-Nan Lien A paper was written some time ago about the general partitioning problem. It's NP-complete. Not trivial. I would like to get some references for the work that has been done on this problem. Can anyone help? Marv Graham; Convex Computer Corp. {allegra,ihnp4,uiucdcs,ctvax}!convex!graham
cdp@uicsrd.UUCP (03/13/87)
Again see the 1986 ICPP proceedings.
lien@osu-eddie.UUCP (03/15/87)
From: Yao-Nan Lien <lien> >From: segall@caip.RUTGERS.EDU (Ed Segall) > >I would like to pose a question to the net: What about solutions >(approximate or exact) to the static communication/computation >balancing problem, which remove this constraint? [see ref below] > >In explanation: Suppose you are willing to have communication paths of >length greater than 1, and you are willing to have 0, 1 or more >processes per processor. Obviously, the minimum communication >embedding would be achieved by locating all processes on one >processor. This solution would have no communication overhead, but >could take far too long to compute! > >In order to avoid this, charge a penalty for unbalancing the >computation load (putting disparate amounts of computation load >on different processors). Also charge penalties for long communication >paths, so that the minimum cost embedding is a combination of >low communication and balanced computation. Minimizing the communication overhead is already very hard to solve. Mixing with processor balance problem together makes the problem more difficult. Even worth, a good modle may not be easy to get either. For example, I don't know how to put minimization problem and balance problem together. (Actually, a bruce force modeling may be possible, but the problem may become intractable.) Penalizing unbalanced the processor may be a good way to approximately transforming the balancing problem to a minimization problem. In this way, we can have either a two-objective minimization problem or a single-objective minimization problem that combines two objectives together. Another alternative is to replace the balance constraint with the processor capability constraints. This makes the problem looking like a MULTI-COMMODITY WAREHOUSE LOCAITON problem in operations research area or the FILE ALLOCATION PROBLEM in distributed database area. Both of them are NP-complete. > >Some work has been done in this area. Craig Steele did an M.S. thesis >at Caltech on just this subject ('85, I think). He modeled the problem >to consider memory requirements and I/O, as well. > >(1) I would like to know if the balancing problem, as stated, is >NP-complete. I suspect it is, but that doesn't mean much. I believe >Steele said it was, but I don't think he showed how to map this >problem to one of the 'known' NP-complete problems. Because of the >above-mentioned difference between this and subgraph isomorphism, I'm >interested in futher explanation. I don't suspect its NP-completeness. It may be be too hard to prove. Such a proof may not be worth to publish in a journal paper. I guess either nobody want to do it, or the proof is buried in some places. > >(2) I am very interested in other approximate solutions. > > >One caveat: this is a hard problem. I am primarily interested in >finding about well-analyzed solutions. It's easy to think up lots of >'intuitive' solutions to this problem. Many people have, including >myself. What's difficult is figuring out if a solution is any good, >or if it even makes sense. However, all ideas are welcome. > As long as optimal solutions are too long to compute, there is always a need to design approximate solutions for different applications. No single approximate solution can be better all other solutions in all cases. I agree that it is very easy to invent intuitive solutions and what more important is to evaluate them. I am also interested in comparing different solutions analytically. This is not a easy job. Yao-Nan Lien