Однокубитное преобразование вектора-состояния - История изменений

ASA в 12:56, 19 июля 2022

2022-07-19T12:56:51Z

← Предыдущая версия		Версия от 12:56, 19 июля 2022
Строка 139:		Строка 139:
	Основной способ параллельной реализации очевиден - необходимо распараллеливание основного цикла (параллельное вычисление различных компонент выходного вектора-состояния) и, желательно, операций умножения. На машинах с общей памятью такой вариант распараллеливания приводит к ускорению, близкому к максимально-возможному.		Основной способ параллельной реализации очевиден - необходимо распараллеливание основного цикла (параллельное вычисление различных компонент выходного вектора-состояния) и, желательно, операций умножения. На машинах с общей памятью такой вариант распараллеливания приводит к ускорению, близкому к максимально-возможному.
	Однако, данный способ сталкивается с проблемами локальности данных. Анализируя математическая описание и информационные графы алгоритма легко видеть, что при использовании большого числа узлов с собственной памятью количество необходимых пересылок между узлами становится сопоставимым с количеством вычислений, что приводит к существенной потере эффективности. Возможны разные пути частичного решения этой проблемы, например, кэширование или использование парадигмы программирования SHMEM, однако, столь сильная нелокальность использования данных всё равно не позволяет добиться хорошей эффективности.		Однако, данный способ сталкивается с проблемами локальности данных. Анализируя математическая описание и информационные графы алгоритма легко видеть, что при использовании большого числа узлов с собственной памятью количество необходимых пересылок между узлами становится сопоставимым с количеством вычислений, что приводит к существенной потере эффективности. Возможны разные пути частичного решения этой проблемы, например, кэширование или использование парадигмы программирования SHMEM, однако, столь сильная нелокальность использования данных всё равно не позволяет добиться хорошей эффективности.

			Алгоритм реализован (в основном последовательные версии) в различных библиотеках для квантовой информатики и квантового компьютерного моделирования. Например: QLib, libquantum, QuantumPlayground, LIQUiD.

	=== Результаты прогонов ===		=== Результаты прогонов ===

ASA в 12:51, 19 июля 2022

2022-07-19T12:51:12Z

Внесённые изменения

ASA: /* Масштабируемость реализации алгоритма */

2022-04-28T14:13:55Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 14:13, 28 апреля 2022
Строка 213:		Строка 213:
	По результатам исследования можно сделать вывод о том, что эффективность алгоритма не является высокой, однако достаточно быстро возрастает с ростом размера задачи. Сложность задачи возрастает экспоненциально и потому имеет смысл решать задачу максимального размера, влезающую в оперативную память, чтобы увеличить общую эффективность вычислений.		По результатам исследования можно сделать вывод о том, что эффективность алгоритма не является высокой, однако достаточно быстро возрастает с ростом размера задачи. Сложность задачи возрастает экспоненциально и потому имеет смысл решать задачу максимального размера, влезающую в оперативную память, чтобы увеличить общую эффективность вычислений.

	Исследованная [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/Scalability/blob/master/qbit/main.cpp параллельная реализация алгоритма]		Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/qbit/main.cpp параллельная реализация алгоритма]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

ASA: /* Количественная оценка локальности */

2022-04-28T14:13:13Z

Количественная оценка локальности

← Предыдущая версия		Версия от 14:13, 28 апреля 2022
Строка 168:		Строка 168:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/qubit_evolution/qubit_evolution.h здесь] (функция Kernel). Условия запуска описаны [~~http~~://~~git~~.~~parallel~~.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/benchmarks/qubit_evolution/qubit_evolution.h здесь] (функция Kernel). Условия запуска описаны [https://gitlab.srcc.msu.ru/shvets.pavel.srcc/locality/blob/master/README.md здесь].

	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

AntonChupin в 13:13, 8 июля 2016

2016-07-08T13:13:57Z

← Предыдущая версия		Версия от 13:13, 8 июля 2016
Строка 252:		Строка 252:

	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]
			[[Категория:Алгоритмы моделирования квантовых систем]]

	[[En:Single-qubit transform of a state vector]]		[[En:Single-qubit transform of a state vector]]

ASA в 06:50, 18 июня 2016

2016-06-18T06:50:09Z

← Предыдущая версия		Версия от 06:50, 18 июня 2016
Строка 251:		Строка 251:
	<references />		<references />

	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]
	[[En:Single-qubit transform of a state vector]]		[[En:Single-qubit transform of a state vector]]

Chernyavskiy в 08:54, 16 июня 2016

2016-06-16T08:54:46Z

← Предыдущая версия		Версия от 08:54, 16 июня 2016
Строка 252:		Строка 252:

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
			[[En:Single-qubit transform of a state vector]]

Teplov: /* Динамические характеристики и эффективность реализации алгоритма */

2016-02-07T15:40:13Z

Динамические характеристики и эффективность реализации алгоритма

@@ Строка 216: / Строка 216: @@
 === Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===
 Исходя из высочайшей возможности параллелизации и при этом наличия существенной нелокальности обращения к данным, эффективная и хорошо масштабируемая параллельная реализация алгоритма однокубитного квантового преобразования легко достижима на машинах с общей памятью. Реализация же на машинах с разделяемой памятью имеет низкую эффективность и требует специальных подходов для уменьшения времени работы. Можно отметить, что данная задача является хорошим плацдармом для разработки методов решения задач с интенсивным использованием данных и низкой локальностью.

Teplov: /* Масштабируемость реализации алгоритма */

2015-12-25T12:33:07Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 12:33, 25 декабря 2015
Строка 213:		Строка 213:
	По результатам исследования можно сделать вывод о том, что эффективность алгоритма не является высокой, однако достаточно быстро возрастает с ростом размера задачи. Сложность задачи возрастает экспоненциально и потому имеет смысл решать задачу максимального размера, влезающую в оперативную память, чтобы увеличить общую эффективность вычислений.		По результатам исследования можно сделать вывод о том, что эффективность алгоритма не является высокой, однако достаточно быстро возрастает с ростом размера задачи. Сложность задачи возрастает экспоненциально и потому имеет смысл решать задачу максимального размера, влезающую в оперативную память, чтобы увеличить общую эффективность вычислений.

	Исследованная [http://git.algowiki-project.org/Teplov/Scalability/~~tree~~/master/~~cholesky-decomposition-master~~ параллельная реализация алгоритма]		Исследованная [http://git.algowiki-project.org/Teplov/Scalability/blob/master/qbit/main.cpp параллельная реализация алгоритма]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Teplov: /* Масштабируемость реализации алгоритма */

2015-12-25T11:47:39Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 11:47, 25 декабря 2015
Строка 212:		Строка 212:

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

			Исследованная [http://git.algowiki-project.org/Teplov/Scalability/tree/master/cholesky-decomposition-master параллельная реализация алгоритма]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===