The following problem is from a classic paper on the method of simulated anneali
ID: 1715006 • Letter: T
Question
The following problem is from a classic paper on the method of simulated annealing for solving optimization problems. Here, we only calculate the number of solutions that are involved in the problem. The method of simulated annealing is a clever way of finding an optimal solution.
When the design of an integrated circuit becomes too complex, the circuitry must be placed on more than one chip. For simplicity, we consider using two chips. The goal then becomes to minimize the number of connections between chips in order to maximize speed and minimize pin count. For large circuits, we may identify circuit blocks and consider the problem of deciding how the blocks of circuitry should be allocated to two chips.
Calculate the number of solutions that are possible for the following scenarios of the circuit-block allocation problem. Note that a solution that differs from another only in which chip is called chip 1 and which is called chip 2 is not a different solution. Also, having zero circuit blocks on one chip is not an allowed solution.
a) 6 circuit blocks
b) 6 circuit blocks but two of the blocks are identical
Explanation / Answer
a)
scienario 1
1 circuit block on chip 1 and 5 one chip 2
scienario 2
2 circuit block on chip 1 and 4 one chip 2
scienario 3
3 circuit block on chip 1 and 3 one chip 2
b)
if 2 circuit blocks ar identicle then we can consider only placing 5 blocks
scienario 1
1 circuit block on chip 1 and 4 one chip 2
scienario 2
2 circuit block on chip 1 and 3 one chip 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.