Possible algorithm not mentioned in class:
1. Find another person/group
2. Add your numbers together
3. Repeat steps 1 and 2 until there's one final solution.
Less idling than the row/column algorithm devised in class.
-o4
One possible way to parallel the computation in this task might be: 1. Create a Google Spreadsheet 2. Each one of us fill in a value corresponding to row/column of our seats 3. Sum the numbers all up easily with the spreadsheet.
billdqu
@-o4, your algorithm is awesome. It is just like multiple threads write to different memory addresses with pre-negotiated rules. It saves lots of communication cost, only needs to care about when will every needed place be filled.
pdp
Isn't writing to memory huge overload? You mean writing to cache? I think one improvement to what we did in class was to start the addition from either ends of each row and add when we meet in the middle of the row. Then, the middle column could do the same thing.
Ant
@-o4, @billdqu - there are some interesting questions to think about here.
How would you determine if every necessary cell of the spreadsheet has been filled (if a Google-owned processor somewhere wasn't doing this for you, and you had to do it yourself)?
If the Google Spreadsheet didn't perform the addition for you, how would you go about doing it efficiently? Fast?
-o4
@Ant, yeah I have to admit I was assuming another Google processor here doing the addition for us. Yes you raised a great point about performing this addition. It still remains a task to solve (my method cheated a bit in this sense). My approach mainly seek to use parallelism to minimize the blocking situation that happened during class.
woohoo
@-04 I like your algorithm but believe it still has quite a bit of communication cost, specifically in distributing the google spreadsheet. would you gather emails from everybody in the class? distribute it through a broadcast system (piazza)?
-o4
@woohoo What I had in mind was to distribute the Google spreadsheet link on screen. Think of it as passing a memory location of the 2D array as extra parameter to each compute(). There are some gaps in this analogy and but you know the idea (more of a proof of concept).
yulunt
The spreadsheet approach is good to reduce communication but synchronization is required to recorded whether all thread finish. For example, pthread_join is called after pthread_create. As for sample code in assignment 1, the program perform join from thread ID 0 to N. There is an another issue here. The order in which threads finish may not correspond to their IDs.
jk2d
@VersaceGohan This indeed creates less idling than the row/column algorithm in class. One thing to consider is that this algorithm quickly leads to the case where people have to add two large number together (2-digit number + 2 digit number or even 3-digit + 3-digit). Human's calculating ability is limited. This could potentially create more overhead, but overall I think your algorithm is still much better than the algorithm used in class.
Possible algorithm not mentioned in class: 1. Find another person/group 2. Add your numbers together 3. Repeat steps 1 and 2 until there's one final solution. Less idling than the row/column algorithm devised in class.
One possible way to parallel the computation in this task might be: 1. Create a Google Spreadsheet 2. Each one of us fill in a value corresponding to row/column of our seats 3. Sum the numbers all up easily with the spreadsheet.
@-o4, your algorithm is awesome. It is just like multiple threads write to different memory addresses with pre-negotiated rules. It saves lots of communication cost, only needs to care about when will every needed place be filled.
Isn't writing to memory huge overload? You mean writing to cache? I think one improvement to what we did in class was to start the addition from either ends of each row and add when we meet in the middle of the row. Then, the middle column could do the same thing.
@-o4, @billdqu - there are some interesting questions to think about here.
How would you determine if every necessary cell of the spreadsheet has been filled (if a Google-owned processor somewhere wasn't doing this for you, and you had to do it yourself)?
If the Google Spreadsheet didn't perform the addition for you, how would you go about doing it efficiently? Fast?
@Ant, yeah I have to admit I was assuming another Google processor here doing the addition for us. Yes you raised a great point about performing this addition. It still remains a task to solve (my method cheated a bit in this sense). My approach mainly seek to use parallelism to minimize the blocking situation that happened during class.
@-04 I like your algorithm but believe it still has quite a bit of communication cost, specifically in distributing the google spreadsheet. would you gather emails from everybody in the class? distribute it through a broadcast system (piazza)?
@woohoo What I had in mind was to distribute the Google spreadsheet link on screen. Think of it as passing a memory location of the 2D array as extra parameter to each compute(). There are some gaps in this analogy and but you know the idea (more of a proof of concept).
The spreadsheet approach is good to reduce communication but synchronization is required to recorded whether all thread finish. For example, pthread_join is called after pthread_create. As for sample code in assignment 1, the program perform join from thread ID 0 to N. There is an another issue here. The order in which threads finish may not correspond to their IDs.
@VersaceGohan This indeed creates less idling than the row/column algorithm in class. One thing to consider is that this algorithm quickly leads to the case where people have to add two large number together (2-digit number + 2 digit number or even 3-digit + 3-digit). Human's calculating ability is limited. This could potentially create more overhead, but overall I think your algorithm is still much better than the algorithm used in class.