Parallelize behavior

Question

I'm trying to understand some quirks of the Parallelize[] behavior.

If I do:

CloseKernels[];
LaunchKernels[1]
f[n_, g_] := 
  First@AbsoluteTiming[
    g[Product[Mod[i, 2], {i, 1, n/2}]
      Product[Mod[i, 2], {i, n/2 + 1, n}]]];
Clear[a, b];
a = Table[f[i, Identity], {i, 100000, 1500000, 100000}];
LaunchKernels[1]
b = Table[f[i, Parallelize], {i, 100000, 1500000, 100000}];
ListLinePlot[{a, b}, PlotStyle -> {Red, Blue}]   

The result is the expected one: CPU utilization:

But if I do the same, changing the function to evaluate:

CloseKernels[];
LaunchKernels[1]
f[n_, g_] := 
  First@AbsoluteTiming[
    g[Product[Sin@i, {i, 1, n/2}] 
      Product[Sin@i, {i, n/2 + 1, n}]]];
Clear[a, b];
a = Table[f[i, Identity], {i, 1000, 15000, 1000}];
LaunchKernels[1]
b = Table[f[i, Parallelize], {i, 1000, 15000, 1000}];
ListLinePlot[{a, b}, PlotStyle -> {Red, Blue}] 

The result is:

CPU utilization:

I think I am missing some important knowledge about Parallelize[] to understand this.

Any hints?

Answer 1

To understand what is going on behind the scenes when using Parallelize, it's a good idea to enable the Parallel Computing Toolkit's debugging mode, i.e.:

Needs["Parallel`Debug`"]
SetOptions[$Parallel, Tracers -> {SendReceive}]

The second example produces a lot of MathLink communication overhead, because the Sin function applied to an integer number is not immediately evaluated by Mathematica (as Leonid Shifrin already mentioned):

Here's a portion of the debugging output:

SendReceive: Receiving from kernel 13: Subscript[iid, 105][Sin[1] Sin[2] Sin[3] Sin[4] Sin[5] Sin[6] Sin[7] Sin[8] Sin[9] Sin[10] Sin[11] Sin[12] Sin[13] Sin[14] Sin[15] Sin[16] Sin[17] Sin[18] Sin[19] Sin[20] Sin[21] Sin[22] Sin[23] Sin[24] Sin[25] Sin[26] Sin[27] Sin[28] Sin[29] Sin[30] Sin[31] Sin[32] Sin[33] Sin[34] Sin[35] Sin[36] Sin[37] Sin[38] Sin[39] Sin[40] Sin[41] Sin[42] Sin[43] Sin[44] Sin[45] Sin[46] Sin[47] Sin[48] Sin[49] Sin[50] Sin[51] Sin[52] Sin[53] Sin[54] Sin[55] Sin[56] Sin[57] Sin[58] Sin[59] Sin[60] Sin[61] Sin[62] Sin[63] Sin[64] Sin[65] Sin[66] Sin[67] Sin[68] Sin[69] Sin[70] Sin[71] Sin[72] Sin[73] Sin[74] Sin[75] Sin[76] Sin[77] Sin[78] Sin[79] Sin[80] Sin[81] Sin[82] Sin[83] Sin[84] Sin[85] Sin[86] Sin[87] Sin[88] Sin[89] Sin[90] Sin[91] Sin[92] Sin[93] Sin[94] Sin[95] Sin[96] Sin[97] Sin[98] Sin[99] Sin[100] Sin[101] Sin[102] Sin[103] Sin[104] Sin[105] Sin[106] Sin[107] Sin[108] Sin[109] Sin[110] Sin[111] Sin[112] Sin[113] Sin[114] Sin[115] Sin[116] Sin[117] Sin[118] Sin[119] Sin[120] Sin[121] Sin[122] Sin[123] Sin[124] Sin[125] Sin[126] Sin[127] Sin[128] Sin[129] Sin[130] Sin[131] Sin[132] Sin[133] Sin[134] Sin[135] Sin[136] Sin[137] Sin[138] Sin[139] Sin[140] Sin[141] Sin[142] Sin[143] Sin[144] Sin[145] Sin[146] Sin[147] Sin[148] Sin[149] Sin[150] Sin[151] Sin[152] Sin[153] Sin[154] Sin[155] Sin[156] Sin[157] Sin[158] Sin[159] Sin[160] Sin[161] Sin[162] Sin[163] Sin[164] Sin[165] Sin[166] Sin[167] Sin[168] Sin[169] Sin[170] Sin[171] Sin[172] Sin[173] Sin[174] Sin[175] Sin[176] Sin[177] Sin[178] Sin[179] Sin[180] Sin[181] Sin[182] Sin[183] Sin[184] Sin[185] Sin[186] Sin[187] Sin[188] Sin[189] Sin[190] Sin[191] Sin[192] Sin[193] Sin[194] Sin[195] Sin[196] Sin[197] Sin[198] Sin[199] Sin[200] Sin[201] Sin[202] Sin[203] Sin[204] Sin[205] Sin[206] Sin[207] Sin[208] Sin[209] Sin[210] Sin[211] Sin[212] Sin[213] Sin[214] Sin[215] Sin[216] Sin[217] Sin[218] Sin[219] Sin[220] Sin[221] Sin[222] Sin[223] Sin[224] Sin[225] Sin[226] Sin[227] Sin[228] Sin[229] Sin[230] Sin[231] Sin[232] Sin[233] Sin[234] Sin[235] Sin[236] Sin[237] Sin[238] Sin[239] Sin[240] Sin[241] Sin[242] Sin[243] Sin[244] Sin[245] Sin[246] Sin[247] Sin[248] Sin[249] Sin[250] Sin[251] Sin[252] Sin[253] Sin[254] Sin[255] Sin[256] Sin[257] Sin[258] Sin[259] Sin[260] Sin[261] Sin[262] Sin[263] Sin[264] Sin[265] Sin[266] Sin[267] Sin[268] Sin[269] Sin[270] Sin[271] Sin[272] Sin[273] Sin[274] Sin[275] Sin[276] Sin[277] Sin[278] Sin[279] Sin[280] Sin[281] Sin[282] Sin[283] Sin[284] Sin[285] Sin[286] Sin[287] Sin[288] Sin[289] Sin[290] Sin[291] Sin[292] Sin[293] Sin[294] Sin[295] Sin[296] Sin[297] Sin[298] Sin[299] Sin[300] Sin[301] Sin[302] Sin[303] Sin[304] Sin[305] Sin[306] Sin[307] Sin[308] Sin[309] Sin[310] Sin[311] Sin[312] Sin[313] Sin[314] Sin[315] Sin[316] Sin[317] Sin[318] Sin[319] Sin[320] Sin[321] Sin[322] Sin[323] Sin[324] Sin[325] Sin[326] Sin[327] Sin[328] Sin[329] Sin[330] Sin[331] Sin[332] Sin[333] Sin[334] Sin[335] Sin[336] Sin[337] Sin[338] Sin[339] Sin[340] Sin[341] Sin[342] Sin[343] Sin[344] Sin[345] Sin[346] Sin[347] Sin[348] Sin[349] Sin[350] Sin[351] Sin[352] Sin[353] Sin[354] Sin[355] Sin[356] Sin[357] Sin[358] Sin[359] Sin[360] Sin[361] Sin[362] Sin[363] Sin[364] Sin[365] Sin[366] Sin[367] Sin[368] Sin[369] Sin[370] Sin[371] Sin[372] Sin[373] Sin[374] Sin[375] Sin[376] Sin[377] Sin[378] Sin[379] Sin[380] Sin[381] Sin[382] Sin[383] Sin[384] Sin[385] Sin[386] Sin[387] Sin[388] Sin[389] Sin[390] Sin[391] Sin[392] Sin[393] Sin[394] Sin[395] Sin[396] Sin[397] Sin[398] Sin[399] Sin[400] Sin[401] Sin[402] Sin[403] Sin[404] Sin[405] Sin[406] Sin[407] Sin[408] Sin[409] Sin[410] Sin[411] Sin[412] Sin[413] Sin[414] Sin[415] Sin[416] Sin[417] Sin[418] Sin[419] Sin[420] Sin[421] Sin[422] Sin[423] Sin[424] Sin[425] Sin[426] Sin[427] Sin[428] Sin[429] Sin[430] Sin[431] Sin[432] Sin[433] Sin[434] Sin[435] Sin[436] Sin[437] Sin[438] Sin[439] Sin[440] Sin[441] Sin[442] Sin[443] Sin[444] Sin[445] Sin[446] Sin[447] Sin[448] Sin[449] Sin[450] Sin[451] Sin[452] Sin[453] Sin[454] Sin[455] Sin[456] Sin[457] Sin[458] Sin[459] Sin[460] Sin[461] Sin[462] Sin[463] Sin[464] Sin[465] Sin[466] Sin[467] Sin[468] Sin[469] Sin[470] Sin[471] Sin[472] Sin[473] Sin[474] Sin[475] Sin[476] Sin[477] Sin[478] Sin[479] Sin[480] Sin[481] Sin[482] Sin[483] Sin[484] Sin[485] Sin[486] Sin[487] Sin[488] Sin[489] Sin[490] Sin[491] Sin[492] Sin[493] Sin[494] Sin[495] Sin[496] Sin[497] Sin[498] Sin[499] Sin[500]] (q=0)

Answer 2

Try this version and I'm sure you will know what's going on.

CloseKernels[];
LaunchKernels[1]
f[n_, g_] := 
  First@AbsoluteTiming[
    g[Product[Sin@i, {i, 1, n/2}] Product[Sin@i, {i, n/2 + 1, n}]]];
Clear[a, b];
a = Table[f[i, Identity], {i, 1000, 15000, 1000}];
LaunchKernels[1]
b1 = Table[f[i, Parallelize], {i, 1000, 15000, 1000}];
b2 = Table[f[i, Parallelize], {i, 1000., 15000., 1000.}];
ListLinePlot[{a, b1, b2}, PlotStyle -> {Red, Blue, Green}]

Answer 3

My guess is that the problem is not in Parallelize, but in what you are trying to compute. For Mod, the result is always either 1 or 0 and the product as well. For Sin, since you use the integer arithmetic, you accumulate huge symbolic expressions (products of Sin[i]). They are discarded after having been computed, but they need the heap space (memory allocation/deallocation). The quadratic behavior you observe is likely due to the linear complexity of large size memory allocation, "multiplied" by the liner complexity from your iteration. This seems the dominant effect, which shadows the real costs of Parallelize. If you apply N, like Sin@N[i], the results are quite different.