"Готовая сразу" мат. модель компа с неограниченными "лучами данных". Ужасная, но корректная.
Mar 03, 2021 12:01
Дописал я математическую модель («архитектуру») для компьютера, представляющего собой центральный процессор и бесконечные лучи данных. Я рассказывал чуть раньше (7 февраля 2021), что доделываю эту модель:
На базе этой модели можно сделать настоящий комп, в котором доступную для процессора оперативную память можно наращивать неограниченно и это никакой смены разрядности ни процессора, ни замены каналов передачи данных в/из оперативной памяти - не потребует. Нужно ещё в формат Латех переводить и т.д. эти 100 с лишним страниц...
Эх! Когда уже практически дописал, оказалось, что можно было и не мучиться полгода. Есть альтернатива. Она чудовищна :)) Ладно, всё равно та красивая модель, что я сделал - нужна. Просто можно было бы её отложить и быстро сделать что просили со статьёй о теории. А теперь я столько всего узнал, что не могу не переписать основательно вводную часть и в теоретической статье. Надеюсь, до конца марта успею всё сделать и отправить тем добрым людям, кого так адски задерживаю. Они уже забыли про меня возможно и/или рассердились :-(
Так вот, приведу кусочек из вводной части (которую переписываю) теоретической статьи про «ужасную модель» (до конца записи):
[Начало (его не менял) про математическую модель вычислительной машины из старой редакции]Есть затраты по времени, пространству и энергии для проведения вычислений. Разберём это на примере одного из базовых элементов компьютерного вычисления - взятия «подстроки» длиной в один символ (букву) из очень длинной «строки». Берем эту букву из ячейки памяти, и доставляем в центральный процессор.
Итак, рассмотрим получение i-го символа из строки a. Это будет подстрока длиной 1, и команда в тексте программы будет примерно такая:
str(a, i, 1)
Сколько времени займет эта операция для получения соответствующего символа из ячейки памяти компьютера внутрь процессора? Для простоты считаем, что ячейки данных содержат по одному символу, первый символ расположен возле процессора, и все ячейки расположены на одной прямой линии на линейном расстоянии от процессора относительно своих номеров.
До символа от процессора и обратно сигнал идет со скоростью света, затрачивая линейное время относительно i, пусть k_1 × i. И требуется какое-то время c_1 на обработку символа процессором, ещё надо время c_2 на обработку сигнала ячейкой памяти. В сумме получаем t = k_1 * i + c_1 + c_2.
А если мы получаем 2 символа str(a, i, 2) с мест i и i + 1, то разумно предположить, что они придут в процессор по очереди, а ячейка i + 1 расположена на одну единицу расстояния памяти дальше ячейки i. И тогда на это получение уйдёт времени: t = 2 * (k_1 * i + c_1 + c_2) + k_1
Простая, удобная модель, весьма близкая (для подобного радикального упрощения) к практическому устройству компьютеров. Будем считать такое расположение и взаимодействие процессора и строк моделью исполнения алгоритмов с «лучами данных». Условимся, что для любого алгоритма у нас свой вариант данной модели, в которой имеется такое конечное количество лучей данных, которое требуется для исполнения данного алгоритма.
Вообще-то все входные данные (даже любое количество бесконечных строк) можно записать и на 1 луче данных (по аналогии с машиной Тьюринга), записывая сначала все 1-е символы входных аргументов друг за другом, затем все вторые и т.д. Но для повышения скорости вычислений и улучшения наглядности (а наглядность является важным качеством для модели) пусть будет конечное число лучей данных - необходимых для алгоритма.
Увы, сейчас на практике нет таких компьютеров, которые можно было бы масштабировать до предложенной математической модели. Проблема в том, что в качестве математической модели нам необходима неограниченная память на каждом «луче данных», а возможности всех нынешних компьютеров по использованию оперативной памяти (в рамках которой и совершаются строковые операции) ограничены разрядностью своих процессоров.
Я подготовил в принципиальном отношении архитектуру вычислительной машины, для которой доступна возможность неограниченно расширять оперативную память без смены разрядности процессора и без модернизации уже установленной памяти и каналов связи памяти и процессора. Эту архитектуру можно реализовать на практике и она годится для масштабирования до уровня математической модели с неограниченными лучами данных. Назову эту модель Машина исполнения компьютерных алгоритмов, сокращённо - МКА.
Но я не могу ссылаться на эту модель до проверки её рецензентами и публикации. К счастью, нашёлся (через полгода, когда я уже заканчивал построение архитектуры МКА) паллиатив, который ужасно не красивый, но который можно сразу использовать в качестве модели вычислительной системы с центральным процессором и лучами данных. А именно:
Пусть в исходном состоянии у нас ограниченная разрядность процессора, равная m_0, и он может обращаться только к ячейкам, номер позиции которых на их лучах данных находится в пределах фиксированного числа 2^{m_0}. Но, как только процессор пытается обратиться к недоступной ему ячейке памяти с номером N, то текущий процессор заменяется новым процессором с минимальной разрядностью m_1. Минимальной эта разрядность является по отношению к неравенству N ≤ 2^{m_1}. При этом на нужном луче данных прокладывается канал связи, соответствующий новой разрядности, до ячеек с номерами до 2^{m_1} включительно.
Очевидно, что все эти операции по модернизации канала связи и замене процессора являются полиномиальными (даже линейными) по затратам времени на них в сравнении с обращением к ячейке N, которое не потребовало бы данных модернизаций. То есть - у нас есть какая-то «бригада» ИТ-специалистов, которая вместо сигнала (летящего со скоростью света) идет с проводами со скоростью пешехода и меняет канал связи. Это всего лишь в 220 млн. раз медленнее сигнала, если исходить из 1,5 м/с скорости пешехода и 330 млн. м/с для скорости света.
Не удивительно, что мне потребовалось 6 месяцев и момент настроения крайнего нигилизма и желания решить вопрос за минуту, чтобы я отправился в закоулки обитания таких ужасных математических моделей. Но описанная модель - годится, чтобы ссылаться на неё при изложении теории. А про хорошую и красивую модель МКА - нужна отдельная статья (или, скорее, статьи).
Ещё один нюанс упомяну.
При увеличении разрядности появляется дополнительный «проводок» при каждом удвоении размера доступных данных. Значит, площадь поперечного сечения канала связи растёт пропорционально lg(N). Из-за этого начала лучей данных могут перестать умещаться на прежнем удалении от процессора и их придётся сдвинуть на k символов дальше, сделав из луча данных:
1234567890…
«Гармошку», например:
14589… 23670…
Отодвигая на k символов, мы меняем исходную «сферу» начальных ячеек лучей данных на новую сферу. А площадь сферы при этом растёт пропорционально k^2. Очевидно, что надо логарифмическое малое k в сравнении с N, чтобы решить эту небольшую проблему с ростом площади поперечного сечения канала связи. И превращение начала лучей данных в «гармошку» добавит к общим затратам времени меньше, чем любой полином - если смотреть в пределе.
Назовём описанную модель-паллиатив «Машина компьютерных алгоритмов с бригадой увеличения доступной оперативной памяти». Но дальше я буду писать везде в этой статье «Машина компьютерных алгоритмов» (или МКА) подразумевая под этим пока что Машину компьютерных алгоритмов с бригадой увеличения доступной оперативной памяти. А когда-то в будущем люди уже будут знать настоящую «Машину компьютерных алгоритмов» (без бригады) и будут понимать модель именно так.