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: Hypercube
Message-ID: <3312@osu-eddie.UUCP>
Date: Sun, 8-Mar-87 01:27:06 EST
Article-I.D.: osu-eddi.3312
Posted: Sun Mar  8 01:27:06 1987
Date-Received: Sun, 8-Mar-87 18:08:19 EST
Sender: lien@osu-eddie.UUCP
Organization: OSU
Lines: 30

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