How do we get 1/N comm-to-comp ratio for MC scaling?
ekr
In this problem, N is being redefined as the square root of the number of elements done by a single processor, not the square root of the total work (i.e., in the previous slide, N=4, not 12). So, each processor operates on N^2 elements, and only communicates N of them (there's no P involved, since we're defining the number of elements only for a single processor). This means the comm-to-comp ratio is N / N^2 = 1/N.
afa4
@grose: From slide 8: comm-to-comp ratio = P^(1/2) / N for an NxN grid. So for MC scaling the ratio comes out to be P^(1/2) / (N * P^(1/2)) which is (1 / N)
Kapteyn
Isn't the work required O(N^3) though? (See top of slide). Should the communication to computation ratio be N/N^3 = 1/N^2?
Kapteyn
Actually, as I look at this slide some more, I'm getting more confused. The amount of work is stated to increase as O(N^3), meaning that the amount of work in memory constrained scaling increases by a factor that is larger than the factor of increase in the number of processors. If we have four times as many processors, we increase our input size by 4x, which increases the total work by 8x.
The slide says total amount of work is (NP^0.5)^3 = (N^3)(P^1.5). If we divide this across P processors we get N^3P^0.5 work per processor. Each processor incurs O(N) communication cost so that gives us a ratio of N/N^3P^0.5 = 1/(N^2P^(0.5)) meaning the communication to computation ratio is not constant and decreases as number of processors increases because work per processor increases when we do memory constrained scaling in the grid solver case (since the grid takes longer to converge as the grid gets larger).
Can someone please explain where I'm going wrong with my math/logic?
kk
@Kapteyn I agree with your ratio of 1/(N^2P^(0.5)).
We have P * N^2 elements in total, meaning that we have N^2 elements per processor.
The overall work is (P^(1/2) * N)^3 = P^(3/2) * N^3. So the work for each processor is (P^(3/2) * N^3)/P = P^(1/2) * N^3.
Each processor needs to communicate O(N) elements, so the communication-computation ratio should be N/(P^(1/2) * N^3) = 1/(P^(1/2) * N^2).
How do we get 1/N comm-to-comp ratio for MC scaling?
In this problem, N is being redefined as the square root of the number of elements done by a single processor, not the square root of the total work (i.e., in the previous slide, N=4, not 12). So, each processor operates on N^2 elements, and only communicates N of them (there's no P involved, since we're defining the number of elements only for a single processor). This means the comm-to-comp ratio is N / N^2 = 1/N.
@grose: From slide 8: comm-to-comp ratio = P^(1/2) / N for an NxN grid. So for MC scaling the ratio comes out to be P^(1/2) / (N * P^(1/2)) which is (1 / N)
Isn't the work required O(N^3) though? (See top of slide). Should the communication to computation ratio be N/N^3 = 1/N^2?
Actually, as I look at this slide some more, I'm getting more confused. The amount of work is stated to increase as O(N^3), meaning that the amount of work in memory constrained scaling increases by a factor that is larger than the factor of increase in the number of processors. If we have four times as many processors, we increase our input size by 4x, which increases the total work by 8x.
The slide says total amount of work is (NP^0.5)^3 = (N^3)(P^1.5). If we divide this across P processors we get N^3P^0.5 work per processor. Each processor incurs O(N) communication cost so that gives us a ratio of N/N^3P^0.5 = 1/(N^2P^(0.5)) meaning the communication to computation ratio is not constant and decreases as number of processors increases because work per processor increases when we do memory constrained scaling in the grid solver case (since the grid takes longer to converge as the grid gets larger).
Can someone please explain where I'm going wrong with my math/logic?
@Kapteyn I agree with your ratio of 1/(N^2P^(0.5)).
We have P * N^2 elements in total, meaning that we have N^2 elements per processor.
The overall work is (P^(1/2) * N)^3 = P^(3/2) * N^3. So the work for each processor is (P^(3/2) * N^3)/P = P^(1/2) * N^3.
Each processor needs to communicate O(N) elements, so the communication-computation ratio should be N/(P^(1/2) * N^3) = 1/(P^(1/2) * N^2).