How do I determine the most efficient algorithm for parallel addition? -



How do I determine the most efficient algorithm for parallel addition? -

after asking question mapreduce algorithm, has got me thinking how determine efficient way of arriving @ total sum of n values using parallel processing. problem can simplified follows:

suppose have n processors, each holding integer. want determine sum of integers possible.

now each processor 2,..,n pass integer processor 1. processor 1 adds each of numbers in turn produce result. means n - 1 passes of data, these can happen in parallel. followed n - 1 add-on operations, occurring in sequence.

alternatively, each odd numbered processor pass integer next numbered processor (let's assume n even, sake of argument). each numbered processor performs 1 add-on operation, in parallel, adding own number 1 it's been passed. end 1/2 n integers add together together. utilize previous method add together remaining values.

of course, there many other ways of doing this. how determine efficient? suspect depends on relative cost of add-on operation vs passing integer (in real life, think cpu vs network speed), , on size of n. after all, if n large, adding network hop in order halve n may worth it, if each add-on relatively cheap.

this more of comment answer, little box confining ...

define most efficient. concerned theoretical efficiency or speed in practice ?

i think you're asking right questions, , seem have realised if have 100,000 processors each 1 integer critical resource communications speed not computation speed. scheme devise sum n integers starting n processors bear in mind communications time dominated not bandwidth (time send 1 integer) latency (time send 0 size message). practical purposes expect issue kill fancy schemes dead.

and question: did integers originate ? if originated on 1 process(or) , distributed other n-1 you've wasted more time sending them out have taken 1st process(or) calculate sum. if integers originated as, perhaps, result of process running on each processor then, no matter (in)efficiency, you'll have kind of reduction anyway , pay communications cost.

in practice you're going boost in speed when calculating sum of n integers on p processors when n much larger p. figure out numbers on parallel computer there's no replacement experimentation.

algorithm parallel-processing

Comments

Post a Comment

Popular posts from this blog

java Multi query from Mysql using netbeans -

java Multi query from Mysql using netbeans - i have java code retrieve info mysql appropriate code in netbeans.the code below. want multi query such illustration finding total number of products , on.could help me please. in advance import java.sql.*; public class javamysqlselectexample { public static void main(string[] args) { seek { string mydriver = "com.mysql.jdbc.driver"; string myurl = "jdbc:mysql://localhost/sample"; class.forname(mydriver); connection conn = drivermanager.getconnection(myurl, "root", "mypasscode1"); string query = "select * products"; statement st = conn.createstatement(); resultset rs = st.executequery(query); while (rs.next()==true) { int code = rs.getint("code"); string productname = rs.getstring("product_name"); string producttype = rs.getstring("product_type"); system.out.format(" %d, %s, %s\n", code, pr
Read more

c# - DotNetZip fails with "stream does not support seek operations" -

c# - DotNetZip fails with "stream does not support seek operations" - i using dotnetzip in c# unzip stream follows: public static void unzipfromstream(stream stream, string outdir) { //omit seek grab block using (zipfile zip = zipfile.read(stream)){ foreach (zipentry e in zip){ e.extract(outdir, extractexistingfileaction.overwritesilently); } } } stream obtained using webclient client = new webclient(); stream fs = client.openread(url); however, got next exception exception during extracting zip stream system.notsupportedexception: stream not back upwards seek operations. @ system.net.connectstream.get_position() @ ionic.zip.zipfile.read(stream zipstream, textwriter statusmessagewriter, encoding encoding, eventhandler`1 readprogress) on server side(asp.net mvc 4), returning filepathresult or filestreamresult both caused exception. should obtain stream differently on client side? or how create server homec
Read more

c++ - StartServiceCtrlDispatcher don't can access 1063 error -

c++ - StartServiceCtrlDispatcher don't can access 1063 error - i write on c++ service , have error, , don't can fixed it. my service main function int main (int argc, tchar *argv[]) {dword f; for(int i=0;i<113;i++) f = getlasterror(); servicepath = lptstr(argv[0]); outputdebugstring(_t("my sample service: main: entry")); //installservice(); service_table_entry servicetable[] = { {service_name, (lpservice_main_function) servicemain}, {null, null} }; // startservice(); if(!startservicectrldispatcher(servicetable)) { f = getlasterror(); //addlogmessage("error: startservicectrldispatcher"); } else if( memcmp(argv[argc-1],"install",7)) { installservice(); } else if( memcmp(argv[argc-1],"remove",6)) { removeservice(); } else if( memcmp(argv[argc-1],"start",5)) { startservice(); } else if( memcmp(argv[argc-1],"stop",4))
Read more