Qt-interest Archive, September 2003
exrta info
Message 1 in thread
A Graph-Theoretic Deterministic Algorithm
Assume that advance information is available
- information describes the average amount of traffic
between each process.
System can be represented as a weighted graph
- each node is a process
- each arc is the flow of messages
Mathematically the problem reduces to finding a way to
cut this graph into k disjoint subgraphs, subject to
some constraints.
- total memory for each subgraph must fit on 1 CPU
- total computational requirement must be satisfiable
by 1 CPU
Goal is then to find the partition that minimizes
communication while still satisfying the basic
constraints.
Partition A:
CPU1| CPU2 | CPU3
| |
V V
A-----B-----C-----D
| \ / \__ / \__ |
| E___ F____ \ |
| / \ / \_\|
G-------H---------I
A-I are communicating processes.
A,E,G run on CPU1
B,F,H run on CPU2
C,D,I run on CPU3
Partition B:
CPU1| CPU2 |CPU3
| |
V V
A-----B-----C-----D
| \ / \__ / \__ |
| E___ F____ \ |
| / \ / \_\|
G-------H---------I
A,E,G runs on CPU1
B,C,F,E runs on CPU2
D,I runs on CPU3
Each arc has a communication weight associated with
it. The arcs that cross CPU boundaries represent
expensive communication in the executing application.
These values are to be minimized.
Graph theoretic algorithms are limited since they
require complete information in advance
Well this is the problem
ALL THE EDGES ARE ASSIGNED SOME WEIGHT
AND EACH TIMEI PARTITION THE GRAPH INTO 3 PARTS I MAY
GET THE DIFFERENT COST(COST MEANS THE TOTAL SUM OF
WEIGHTS FOR THAT PARTICULAR PARTITION
THE ASSIGNMENT IS TO PARTITION THE GRAPH INTO K
SUBGROUPS SUCH THAT THE SUM OF FLOW OF MESSAGES
BETWEEN THE MACHINES(CPU) IS MINIMISED;
ACTUALLY WE R SUPPOSED TO THIS ASSIGNMENT WITH UNIX-C
BUT I REALLY WANT TO TRY QT HERE AND DONT HAVE ANY
IDEA IF IT IS POSSIBLE.
U CAN SEE THE MODERN OPERATING SYSTEMS BY ANDREW
TANENBUAM
AND IF SOMETHING ELSE JUST PUT FORTH QUERY TO ME I
WILL EXPLAIN ANYTHING RELATED TO IT WITH EXAMPLE
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
Message 2 in thread
>A Graph-Theoretic Deterministic Algorithm
>8
>ACTUALLY WE R SUPPOSED TO THIS ASSIGNMENT WITH UNIX-C
>BUT I REALLY WANT TO TRY QT HERE AND DONT HAVE ANY
>IDEA IF IT IS POSSIBLE.
As Chris allready told you: Qt does not deal with graph theory. What you are
asking is pure math, and Qt doesn't deal with that. Furthermore, I doubt if
anyone here is willing to do your homework, and no, shouting about it won't
help either. Good luck with your assignment. The moment you have a Qt
specific question, feel free to ask it on this group.
André
--
[ signature omitted ]
