Глоссарий - История изменений

ASA: /* Параллельная сложность */

2026-01-16T10:48:03Z

Параллельная сложность

← Предыдущая версия		Версия от 10:48, 16 января 2026
Строка 95:		Строка 95:

	=== Параллельная сложность ===		=== Параллельная сложность ===
	'''Параллельная сложность''' (parallel complexity) алгоритма - ~~число~~ шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической [[#Ярусно-параллельная форма графа алгоритма\|ярусно-параллельной формы]].		'''Параллельная сложность''' (parallel complexity) алгоритма - количество основных вычислительных шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых ресурсов (процессоров, функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической [[#Ярусно-параллельная форма графа алгоритма\|ярусно-параллельной формы]].


	=== Параметры запуска ===		=== Параметры запуска ===

ASA: /* Вычислительная сложность */

2026-01-16T09:50:26Z

Вычислительная сложность

← Предыдущая версия		Версия от 09:50, 16 января 2026
Строка 8:		Строка 8:

	=== Вычислительная сложность ===		=== Вычислительная сложность ===
	'''Вычислительная сложность''' (computational complexity) задачи <math>W</math> - количество основных вычислительных шагов лучшего последовательного алгоритма, необходимых для решения задачи на одном процессоре. Вычислительная сложность обычно является некоторой функцией от размера входных данных ~~программы~~.		'''Вычислительная сложность''' (computational complexity) задачи <math>W</math> - количество основных вычислительных шагов лучшего последовательного алгоритма, необходимых для решения задачи на одном процессоре. Вычислительная сложность обычно является некоторой функцией от размера входных данных рассматриваемого алгоритма.


	=== Вычислительное ядро ===		=== Вычислительное ядро ===

ASA: /* Эквивалентное возмущение */

2025-03-14T10:07:27Z

Эквивалентное возмущение

← Предыдущая версия		Версия от 10:07, 14 марта 2025
Строка 180:		Строка 180:

	=== Эквивалентное возмущение ===		=== Эквивалентное возмущение ===
	'''Эквивалентное возмущение''' (equivalent perturbation) алгоритма - одна из характеристик влияния ошибок округления промежуточных операций на отклонение решения, получаемого алгоритмом, от настоящего решения задачи. Выражается косвенно: влияние ошибок на ответ считается таким же, как если бы данные были заданы с ошибкой, ~~выражаемым~~ эквивалентным возмущением, но задача с такими данными была бы решена точно.		'''Эквивалентное возмущение''' (equivalent perturbation) алгоритма - одна из характеристик влияния ошибок округления промежуточных операций на отклонение решения, получаемого алгоритмом, от настоящего решения задачи. Выражается косвенно: влияние ошибок на ответ считается таким же, как если бы данные были заданы с ошибкой, выражаемой эквивалентным возмущением, но задача с такими данными была бы решена точно.


	=== Эквивалентное преобразование ===		=== Эквивалентное преобразование ===

ASA: /* Производительность */

2025-03-14T10:05:40Z

Производительность

← Предыдущая версия		Версия от 10:05, 14 марта 2025
Строка 122:		Строка 122:
	'''Производительность''' (performance) <math>R=Op/t</math> определяется количеством операций <math>Op</math>, производимых данным компьютером в единицу времени. Для высокопроизводительных вычислений в расчёт обычно берут количество арифметических операций в секунду над вещественными данными, представленными в форме с плавающей точкой. Эта величина называется Flop/s (от английского Floating point operations per second).		'''Производительность''' (performance) <math>R=Op/t</math> определяется количеством операций <math>Op</math>, производимых данным компьютером в единицу времени. Для высокопроизводительных вычислений в расчёт обычно берут количество арифметических операций в секунду над вещественными данными, представленными в форме с плавающей точкой. Эта величина называется Flop/s (от английского Floating point operations per second).

	Поскольку современные суперкомпьютеры производят очень много таких операций в секунду, их производительность измеряется кратными величинами, такими как GFlop/s (<math>10^9</math> операций в секунду), TFlop/s (<math>10^{12}</math>), PFlop/s (<math>10^{15}</math>), EFlop/s (<math>10^{18}</math>). Производительность мощнейших современных суперкомпьютеров уже измеряется в EFlop/s, ~~дёт~~ обсуждение построения систем зеттафлопсного (порядка <math>10^{21}</math> операций в секунду) уровня производительности.		Поскольку современные суперкомпьютеры производят очень много таких операций в секунду, их производительность измеряется кратными величинами, такими как GFlop/s (<math>10^9</math> операций в секунду), TFlop/s (<math>10^{12}</math>), PFlop/s (<math>10^{15}</math>), EFlop/s (<math>10^{18}</math>). Производительность мощнейших современных суперкомпьютеров уже измеряется в EFlop/s, идёт обсуждение построения систем зеттафлопсного (порядка <math>10^{21}</math> операций в секунду) уровня производительности.

	=== Профиль обращений в память ===		=== Профиль обращений в память ===

ASA: /* Производительность */

2025-03-14T10:04:54Z

Производительность

← Предыдущая версия		Версия от 10:04, 14 марта 2025
Строка 122:		Строка 122:
	'''Производительность''' (performance) <math>R=Op/t</math> определяется количеством операций <math>Op</math>, производимых данным компьютером в единицу времени. Для высокопроизводительных вычислений в расчёт обычно берут количество арифметических операций в секунду над вещественными данными, представленными в форме с плавающей точкой. Эта величина называется Flop/s (от английского Floating point operations per second).		'''Производительность''' (performance) <math>R=Op/t</math> определяется количеством операций <math>Op</math>, производимых данным компьютером в единицу времени. Для высокопроизводительных вычислений в расчёт обычно берут количество арифметических операций в секунду над вещественными данными, представленными в форме с плавающей точкой. Эта величина называется Flop/s (от английского Floating point operations per second).

	Поскольку современные суперкомпьютеры производят очень много таких операций в секунду, их производительность измеряется кратными величинами, такими как GFlop/s (<math>10^9</math> операций в секунду), TFlop/s (<math>10^12</math>), PFlop/s (<math>10^15</math>). Производительность мощнейших современных суперкомпьютеров уже измеряется ~~десятками PFlop~~/s, ~~активно идёт~~ обсуждение построения систем ~~экзафлопсного~~ (порядка <math>10^18</math> операций в секунду) уровня производительности.		Поскольку современные суперкомпьютеры производят очень много таких операций в секунду, их производительность измеряется кратными величинами, такими как GFlop/s (<math>10^9</math> операций в секунду), TFlop/s (<math>10^{12}</math>), PFlop/s (<math>10^{15}</math>), EFlop/s (<math>10^{18}</math>). Производительность мощнейших современных суперкомпьютеров уже измеряется в EFlop/s, дёт обсуждение построения систем зеттафлопсного (порядка <math>10^{21}</math> операций в секунду) уровня производительности.


	=== Профиль обращений в память ===		=== Профиль обращений в память ===

Анюшева Ирина: /* Граф алгоритма */

2017-02-07T09:54:29Z

Граф алгоритма

← Предыдущая версия		Версия от 09:54, 7 февраля 2017
Строка 18:		Строка 18:
	'''Граф алгоритма''' (algorithm graph) - это ориентированный ациклический мультиграф, вершины которого соответствуют операциям алгоритма, а дуги - передаче данных между ними. Вершины графа алгоритма могут соединяться несколькими дугами, в частности когда в качестве разных аргументов одной и той же операции используется одна и та же величина. Граф алгоритма почти всегда является параметризованным графом. В частности, его вид часто зависит от входных данных.		'''Граф алгоритма''' (algorithm graph) - это ориентированный ациклический мультиграф, вершины которого соответствуют операциям алгоритма, а дуги - передаче данных между ними. Вершины графа алгоритма могут соединяться несколькими дугами, в частности когда в качестве разных аргументов одной и той же операции используется одна и та же величина. Граф алгоритма почти всегда является параметризованным графом. В частности, его вид часто зависит от входных данных.

	Граф алгоритма используется как удобное представление алгоритма при исследовании его структуры, ресурса параллелизма, а также других свойств. Его можно рассматривать как параметризованную информационную историю. Он сохраняет её информативность, при ~~это~~ обладая компактностью за счёт параметризации. Разработана методика построения графа алгоритма по исходному тексту программ.		Граф алгоритма используется как удобное представление алгоритма при исследовании его структуры, ресурса параллелизма, а также других свойств. Его можно рассматривать как параметризованную информационную историю. Он сохраняет её информативность, при этом обладая компактностью за счёт параметризации. Разработана методика построения графа алгоритма по исходному тексту программ.

	''См. также: [https://ru.wikipedia.org/wiki/Граф_алгоритма Граф алгоритма]''		''См. также: [https://ru.wikipedia.org/wiki/Граф_алгоритма Граф алгоритма]''


	=== Детерминированность ===		=== Детерминированность ===

AntonChupin в 12:28, 8 июля 2016

2016-07-08T12:28:06Z

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

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
			[[Категория:Algowiki:Справка]]

ASA в 13:32, 10 февраля 2016

2016-02-10T13:32:07Z

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

Frolov в 10:42, 2 декабря 2015

2015-12-02T10:42:50Z

← Предыдущая версия		Версия от 10:42, 2 декабря 2015
Строка 167:		Строка 167:

	=== Скошенный параллелизм ===		=== Скошенный параллелизм ===
	'''Скошенный параллелизм''' (skewed parallelism) - параллелизм в пространстве итераций, определяемый поверхностями уровней разверток.		'''Скошенный параллелизм''' (skewed parallelism) - параллелизм в пространстве итераций, определяемый поверхностями уровней разверток. Ряд исследователей этим термином пользуется только для случая, когда параллелизм не является [[#Координатный паралеллизм\|координатным]].


Строка 184:		Строка 184:
	'''Суперлинейное ускорение''' (super linear speedup) или '''сверхлинейное ускорение''' программы - это [[#Ускорение\|ускорение]], превосходящие число используемых процессоров p. Чаще всего объясняется эффектом от использования кэш-памяти.		'''Суперлинейное ускорение''' (super linear speedup) или '''сверхлинейное ускорение''' программы - это [[#Ускорение\|ускорение]], превосходящие число используемых процессоров p. Чаще всего объясняется эффектом от использования кэш-памяти.

			=== Суперскалярность ===

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

			''См. также:''
			* ''[https://ru.wikipedia.org/wiki/Суперскалярность Суперскалярность]''

	=== Ускорение ===		=== Ускорение ===

Frolov: /* Избыточные вычисления */

2015-08-28T13:56:43Z

Избыточные вычисления

← Предыдущая версия		Версия от 13:56, 28 августа 2015
Строка 37:		Строка 37:
	* В понимании графовой модели вычислений это такие операции, результаты которых нигде не будут использованы. Такие операции появляются в результате ошибок программирования и подлежат удалению из алгоритма.		* В понимании графовой модели вычислений это такие операции, результаты которых нигде не будут использованы. Такие операции появляются в результате ошибок программирования и подлежат удалению из алгоритма.
	* Распространено также понимание термина как вычисления, которые ''выполняются более одного раза'' или на более чем одном процессоре. Избыточные вычисления могут использоваться либо в многопроцессорных системах, чтобы минимизировать обмены, либо при недостаточном объеме памяти для хранения всех вычисленных значений.		* Распространено также понимание термина как вычисления, которые ''выполняются более одного раза'' или на более чем одном процессоре. Избыточные вычисления могут использоваться либо в многопроцессорных системах, чтобы минимизировать обмены, либо при недостаточном объеме памяти для хранения всех вычисленных значений.
	* Кроме этого, избыточными вычислениями можно назвать те операции, которые появляются при замене последовательного алгоритма ~~специальным параллельным, у которого~~ больше операций, но ~~меньший критический путь~~ графа. В таком случае реальное ускорение параллельного алгоритма следует считать не в сравнении с однопроцессорной реализацией его самого, а в сравнении с реализацией последовательного алгоритма.		* Кроме этого, избыточными вычислениями можно назвать те операции, которые появляются при замене последовательного алгоритма на специальный параллельный. У последнего алгоритма больше операций, но меньше длина критического пути графа, этим и обосновывается замена алгоритма. В таком случае реальное ускорение параллельного алгоритма следует считать не в сравнении с однопроцессорной реализацией его самого, а в сравнении с реализацией последовательного алгоритма. В нашей открытой энциклопедии свойств алгоритмов именно последнее толкование термина применяется в категории [[http://algowiki-project.org/ru/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%81_%D0%B8%D0%B7%D0%B1%D1%8B%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%BC%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F%D0%BC%D0%B8 Алгоритмы с избыточными вычислениями]].

	=== Конечный параллелизм ===		=== Конечный параллелизм ===