barkalov_k_a_metody_parallelnyh_vychislenii_metodicheskoe_po

Параллельные численные методы																			121
		840		30,62		15,38		1,99		7,83		3,91		5,35		5,72		4,14		7,38
		945		34,42		17,23		1,99		8,75		3,93		6,02		5,71		4,64		7,40

	Ускорение
	8
	7							N, млн.
								105
	6							210
								315
	5							420
								525
								630
	4							735
								840
	3							945
	2							Число
	2	3	4	5	6	7	8
								потоков

Рис. 5.7.Ускорение при использовании ПСЧ Табл. 5.2. Экспериментальная оценка ускорения при использовании КСЧ

N,	1 поток	2 потока		4 потока		6 потоков		8 потоков
млн	t, сек	t, сек	S	t, сек	S	t, сек	S	t, сек	S
105	4,16	2,10	1,97	1,07	3,87	0,73	5,68	0,59	7,02
210	8,33	4,18	1,99	2,12	3,92	1,46	5,68	1,10	7,52
315	12,49	6,25	1,99	3,30	3,77	2,20	5,68	1,65	7,56
420	16,64	8,34	1,99	4,21	3,95	2,93	5,67	2,21	7,51
525	20,81	10,46	1,98	5,35	3,88	3,66	5,67	2,74	7,58
630	25,02	12,52	1,99	6,38	3,92	4,41	5,66	3,30	7,56
735	29,18	14,61	1,99	7,53	3,87	5,11	5,70	3,85	7,57
840	33,30	16,73	1,99	8,56	3,88	5,85	5,69	4,41	7,54
945	37,50	18,84	1,99	9,61	3,90	6,63	5,65	4,99	7,51

	122					Параллельные методы Монте-Карло
	Ускорение
	8
	7							N, млн.
								105
	6							210
								315
	5							420
								525
								630
	4							735
								840
	3							945
	2							Число
	2	3	4	5	6	7	8
								потоков
		Рис. 5.8. Ускорение при использовании КСЧ

Количество повторений в проведенных экспериментах специально взято весьма большим с тем, чтобы времена работы функций составляли секунды и влияние накладных расходов (создание потоков, например) было практически нивелировано.

Параллельные численные методы

123

6. Литература

6.1. Использованные источники информации

1.Вержбицкий В.М. Численные методы (математический анализ и обыкновенные дифференциальные уравнения). – М.: Высшая школа, 2001.

2.Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. – М.:

Наука, 1987.

3.Тихонов А.Н., Самарский А.А. Уравнения математической физики. –

М.: Наука, 1977.

4.Самарский А.А., Гулин А.В. Численные методы. – М.: Наука, 1989.

5.Самарский А.А. Введение численные методы. – СПб.: Лань, 2005.

6.Калиткин Н.Н. Численные методы. – М.: Наука, 1978

7.Хамахер К., Вранешич З., Заки С. Организация ЭВМ. –СПб: Питер, 2003.

8.Голуб Дж., Ван Лоун Ч. Матричные вычисления. – М.: Мир, 1999.

9.Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. – М.: Мир, 1984.

10.Писсанецки С. Технология разреженных матриц. — М.: Мир,1988.

11.Соболь И.М. Численные методы Монте-Карло. – М.: Наука, 1973.

12.Соболь И.М. Точки, равномерно заполняющие многомерный куб. – М.: Знание, 1985.

13.Д. Кнут. Искусство программирования. Том 2: получисленные алгоритмы. – М.: «Вильямс», 2007.

14.Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. – Н.Новгород, Изд-во ННГУ, 2003.

15.Гергель В.П. Теория и практика параллельных вычислений. – М.: БИ-

НОМ, 2007.

16.Белов С.А., Золотых Н.Ю. Численные методы линейной алгебры. – Н.Новгород, Изд-во ННГУ, 2005.

17.J. Dongarra et al. Templates for the solution of linear systems: building blocks for iterative methods. SIAM, 1994.

124	Параллельные методы Монте-Карло

18.G. Karniadakis, R. Kirby. Parallel scientific computing in C++ and MPI. Cambridge university press, 2003.

19.M. Quinn. Parallel programming in C with MPI and OpenMP. McGrawHill, 2004.

6.2. Дополнительная литература

20.Ширяев А. Н. Вероятность, – М.: Наука. 1989.

21.Metropolis N., Ulam S. The Monte Carlo method, J. Amer. statistical assoc., 1949, 44, N247, 335-341.

22.O. Percus, M. Kalos. Random number generators for MIMD parallel processors// Journal of parallel and distributed computing, v.6, 1989. pp. 477–479.

23.M. Matsumoto, T. Nishimura (1998). «Mersenne twister: A 623dimensionally equidistributed uniform pseudorandom number generator». ACM Trans. on Modeling and Computer Simulations v. 8(1).

24.M. Mascagni, A. Srinivasan. Algorithm 806: SPRNG: A scalable library for pseudorandom number generation. ACM Transactions on Mathematical Software, v. 26, № 3, 2000. pp. 436–461.

25.Niederreiter H. Random Number Generation and Quasi-Monte Carlo Methods. – SIAM, 1992. – 247 p.

6.3. Информационные ресурсы сети Интернет

26. Intel Math Kernel Library Reference Manual.

[http://software.intel.com/sites/products/documentation/hpc/mkl/mklman.pdf].