A technique for making programs run faster is to first divide the work in the program into a number of threads (tasks), then to assign the threads to a number of nodes (computers) to be executed in parallel. A problem arises because threads need to communicate with each other. When two threads are assigned to different computers, the communication takes place across a computer network and will incur a communication cost.
Your problem is to minimize communication cost between threads across the network. Each node must be assigned the same number of threads. You must find an optimal partition (assignment) of threads to nodes such that the total communication cost is minimized. The communication cost of a partition of threads to nodes is defined as the sum of the communication costs of each pair of threads that are assigned to different nodes. To balance the network load, you must assign equal numbers of threads to each node.
For example, your problem may involve partitioning 4 threads to 2 nodes, where the communication cost between each pair of threads is shown in the table below.
Since the same number of threads must be assigned to each node, each node must be assigned 2 threads. If we put threads 1&3 on the first node, and threads 2&4 on the second node, the communication cost for the partition will be:
cost(1,2) + cost(1,4) + cost(2,3) + cost(3,4) = 14 + 2 + 30 + 39 = 85
The costs for 1,3 and 2,4 were not included because these pairs of threads are assigned to the same node. In comparison, if we put threads 1&2 on the first node, and threads 3&4 on the second node, the communication cost for the partition will be:
cost(1,3) + cost(1,4) + cost(2,3) + cost(2,4) = 27 + 2 + 30 + 11 = 70
The second partition is thus less expensive.
The first line of integers consists of a pair of integers (t,n),
where t is the number of threads and n is the number of nodes.
There will be an additional t lines of input, providing a
grid of communication costs between threads,
where the entry in position [x,y] represents the communication
cost between thread x and y if they are placed on separate nodes.
All costs will be positive integers, and the grid will
be symmetric (i.e., cost of [a,b] will be same as [b,a]).
You may assume that there are at most 10 threads and 10 nodes,
and the number of nodes always evenly divides the number
of threads.
The output consists of one line. Output ``Communication cost: " and the communication cost of the best thread mapping.
Input:
4 2 0 14 27 2 14 0 30 11 27 30 0 39 2 11 39 0
Output:
Communication cost: 70
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |