Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!osu-eddie!lien
From: lien@osu-eddie.UUCP
Newsgroups: comp.arch
Subject: Re: Hypercube (Wrong problem)
Message-ID: <3349@osu-eddie.UUCP>
Date: Sat, 14-Mar-87 22:11:23 EST
Article-I.D.: osu-eddi.3349
Posted: Sat Mar 14 22:11:23 1987
Date-Received: Sun, 15-Mar-87 08:05:34 EST
Sender: lien@osu-eddie.UUCP
Organization: Ohio State Univ, Computer Science Department
Lines: 79

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