Разработка распределённой системы поддержки параллельного исполнения программ, заданных на функциональном языке

Она не станет читать твой диплом...

Классное название, правда? Мне тоже нравится.

Коротко о том, что я писал и что из этого вышло

Задача - автоматическое распараллеливание кода на Scheme. Подход - ленивые вычисления. Написан компилятор в псевдокод и интерпретатор этого псевдокода. Все более-менее переносимо на Windows/Linux/Unix/Mac OS. И даже работает на них (проверялось на Windows XP, Mac OS X, Ubuntu, Mandriva 2007, Debian).

После небольшой доработки напильником в большинстве случаев даже повышалась эффективность. Об этом - ниже, в самом конце.

Запускать так:
compiler <файл_с_исходным_кодом> <выходной_файл>
executer <файл_с_псевдокодом> [<количество_дополнительных_потоков (по умолчанию - 0)>]

Результат защиты - 4 и статус "инженер-ктототам" :)

Если интересно подробнее, то:
text_a5.zip - текст диплома
code.zip - исходный код

Но перед тем, как читать это, прочтите пару страничек ниже :)

Про текст диплома и код на момент сдачи

Извинения

Во-первых, текст оформлен на A5, 10-м Times-ом. Это у нас на факультете стандарт такой. Чтобы нормально читать с экрана, нужно поставить 150%, тогда размер шрифта становится пристойным.

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

В-третьих, совершенно ужасное введение. Не читайте. Точнее, прочтите, потому что всё - правда, но учтите, что это один из тонких грязных трюков. Введение как-бы намекает, что результатом работы будет (или хотя бы может быть) увеличение производительности в 100 раз :) Это совершенно не так. Но поскольку в прямую ничего подобного не обещалось, никто никому и не врал. Нельзя так писать.

В-четвёртых, всё это - одна большая наглость с моей стороны. Чтобы нормально поднять такую тему нужно на порядок больше знаний, чем у меня есть. Наглость прокатывает только потому, что в этой области на моей кафедре никто не знает вообще ничего :) Я на их фоне выгляжу корифеем.

В-пятых, за такое название нужно отрывать руки. Никто не знает, что означает словосочетание "система поддержки параллельного выполнения" :) Тем оно и ценно :))

Что читать

Если вы программист, и хотите разобраться глубоко: Если вы не программист или не хотите разбираться глубоко:

Поправки, ошибки, варианты, дополнения

Эффективность и доработка напильником

История

Это интересно :)

История рассказывается в лучших традициях Конандоиля - детали, по которым читатель может заранее догадаться о развязке просто не приводятся :)

К моменту сдачи, проект не давал никакого прироста производительности ни на каких тестах, ни на каких системах :) При том что особых блокировок, вроде, не было, синхронизация потоков использовалась довольно редко и точечно.

Диплом был сдан, но мне же интересно :) Так что работу я продолжил. Первой проблемой стало отсутствие у меня многопроцессорной машины. Несколько знакомых нашлось (спасибо: Александру Бабаеву, Дмитрию Голубеву, Дмитрию Барышкову), но ни к кому из них не удалось поставить Intel VTune (по разным причинам; а вот потестировать потом удалось на всех). Так что я пошёл на кафедру, там нашёлся свободный двухпроцессорный сервер (спасибо научному руководителю, Игорю Вячеславовичу Стручкову), на который примерно через две недели удалось поставить VTune. Но это я забегаю вперёд, начал я на своей машине, без всяких профайлеров :) Да и потом, появляться в институте чаще чем раз в неделю мне было немного влом...

Первым инсайтом стало наличие критической секции в стандартной библиотеке C. Эта критическая секция блокировала одновременный доступ потоков к куче, поскольку у меня в программе было много выделений памяти, это могло быть узким местом. Обрадовавшись, что нашёл решение, я написал вот такой менеджер памяти: 
#ifdef USE_FAST_ALLOCATOR

namespace allocator
{
	const int blockSize = 1024 * 1024 * 10;

	inline void* malloc(size_t count)
	{
#ifdef _WIN32
		// VC standard
		static __declspec(thread) char* begin = 0;
		static __declspec(thread) char* end = 0;
#else
		// GCC standard
		static __thread char* begin = 0;
		static __thread char* end = 0;
#endif 

		if ((count & 0x0f) != 0)
		{
			// 16-byte address alignment
			count &= ~0x0f;
			count += 0x010;
		}

		if (end - begin < (int)count)
		{
			// need allocate new block
			begin = (char*)::malloc(blockSize);
			end = begin + blockSize;
		}

		char* tmp = begin;
		begin += count;

		return tmp;
	}

	inline void free(const void* po)
	{
	}
}

inline void* operator new (size_t count) throw (std::bad_alloc)
{
	return allocator::malloc(count);
}

inline void operator delete (void* p) throw()
{
	allocator::free(p);
}

#endif

Он не использует блокировки (правда, под Mac OS X нормально скомпилировать это не удалось) и не освобождает память. На XP использование этого менеджера памяти ускоряет работу программы примерно в 3 раза. Но, к сожалению, однопоточная и многопоточная версии ускоряются одинаково. Так что производительности опять не вышло.

После этого я всё-таки поставил VTune и несколькими мелкими изменениями увеличил общую производительность ещё раза в 2. Кстати, VTune реально рулит! Правда, поставить его на Mandriva 2007 нам с научным руководителем так и не удалось (именно из-за этого ушло две недели). Пришлось специально для него ставить XP :) Но, опять таки, все изменения ускоряли обе версии.

Следующим инсайтом стал кэш. Оба процессора стоят на одной системной шине, она является разделяемым ресурсом, и, если кэш используется неэффективно, это может стать узким местом. Исследования на моём компьютере показали, что действительно, куча попаданий мимо кэша. VTune даже насчитал, что если бы они все попали куда надо, было бы сэкономлено 6 секунд - вся программа выполнялась 12 секунд. Поскольку в течении этих 6-и секунд шина занята, второй процессор в это же время не может обратиться к шине, так что если ему не повезёт, он будет просто ждать и простаивать.

С этими теоретическими построениями я пришёл в институт, проверять гипотезу на многопроцессорной машине. И, неожиданно для всех, получил .. повышение производительности при запуске с несколькими потоками :) Время исполнения уменьшилось примерно на 30-40% Причём, с обоими вариантами менеджера памяти. Под бурные овации научного руководителя я завершил работу и побежал проверять результаты у знакомых.

Критичным изменением, видимо, была установка разумного начального значения для размера векторов. В результате количество обращений к памяти уменьшилось в разы. И, хотя память осталась узким местом, оно перестало быть настолько узким.

Результаты

Тест: 
(define func (lambda (x)    
	(if (= x 0)           
		1          
		(* x (func (- x 1)))    
	)
))

(map func 1000 1000 1000)
32-х разрядная Windows XP, 2 процессора Intel EM64 (данные примерные, по памяти):
Windows XP, Intel Core 2 Duo:
Mac OS X, Intel Core 2 Duo (вот чОртова операционная система! на 1000 программа падает, проверяли на 700, кроме того, с быстрым алокатором тоже падает. И всю положительную статистику портит... Не зря их символ - надкусанное яблоко):
Debian Linux (наверное, 64 разряда) 2 процессора Intel EM64:
В общем, есть небольшой, но стабильный выигрыш при использовании 1-го дополнительного потока и быстрого аллокатора. Ещё, обратите внимание на соотношение врёмён real/usr/sys - в случае использования двух или трёх дополнительный потоков, sys очень вырастает, за счёт этого всё работает неэффективно. Правда, usr тоже вырастает, и не совсем понятно, куда же оно уходит :) Но это и на остальных системах непонятно :)

Windows XP, Celeron 2Gz, 512Mb памяти. Это моя машинка :) Процессор один. Тем не менее, при использовании быстрого аллокатора, примерно через три секунды оперативная память кончается и начинается свопинг. Task Manager показывает, что загрузка процессора падает с 100% до 10%, а потом и до 2-3%. В этой ситуации многопоточная версия работает быстрее даже на однопроцессорной машине - пока один поток ждёт окончания свопинга, второй может работать. Эффект не очень большой, но заметный - примероно -20%. Правда, стандартный аллокатор не приводит к свопингу и за счёт этого отрабатывает почти в два раза быстрее. И, конечно, без каких-либо преимуществ для многопоточной версии.

Итого

На этом я считаю свою миссию выполненой. Во всяком случае, на ближайшее будущее.

На главную
Hosted by uCoz