Runtime, memory & scalability

Сколько стоит локальное происхождение: время, память, масштаб

Максим Кирилюк · НИС АДНЖ · 19.11.2026
Данные: Schubert, Andaleon & Wheeler (2020), PeerJ 8:e10090

2000 человек, одно ядро: 8 часов или 6 суток?

Размер задачи — четыре числа

референсная панель RYRICEU когорта: аллели 0/1 2NM маркеров
Nлюди (2N гаплотипов)20…2000
Mмаркеры (SNP)50 000*
Rгаплотипы панели≈ 372
Kпопуляции2

Меняли только N.
Вход при N = 2000: 2·10⁸ аллелей = 25 МБ битами.

* M для этого опыта в статье не назван: 50 000 (хр. 22) или 44 332 (хр. 1); берём 50 000 (±10%). R: 1000G CEU 99 + YRI 108 минус ≈10% основателей — оценка.

I. Время: один гаплотип — динамика за O(M·R)

Loter: src/graph/graph.cpp, EstimateSknn::s_cost_i. Li & Stephens (2003), Genetics 165:2213.

Loter: 160 проходов, и во что они упираются

T ∝ 8λ × 20бутстрэп × 2N × M × R

N = 2000: 1,2·10¹³ клеток.
Соседи по когорте не участвуют ⇒ линейно по N.

Таблица на гаплотип: R × M × 8 Б = 149 МБ — ни в один кэш.

Если упираемся в запись в DRAM:
95 ТБ / 10–20 ГБ/с ≈ 1,3–2,6 ч; замер — 8,1 ч. Тот же порядок.

L1 32 КБ · 1 нсL2 1 МБ · 4 нсL3 30 МБ · 15 нсDRAM сотни ГБ · 100 нс ↑ таблица DP 149 МБ живёт здесь

Типичные порядки для x86-сервера; машина в статье не указана. Оценка, не профиль. Ещё одно слагаемое того же порядка — перекраска на Python: цикл по R номерам панели (local_ancestry.py, clusters_to_list_pop).

RFMix: откуда N²

В каждом окне — случайный лес, обученный на панели: это линейно.

EM-доучивание (-e 2): каждому человеку — свой лес на остальной когорте.

N лесов × 2N примеров ≈ 2N²

Людей ×2 ⇒ лесов ×2, каждый ×2 ⇒ работа ×4.

3 чел. 6 чел. строка — лес одного человека,клетки — его обучающие примеры

По коду RFMix 1.5.4 (main.cpp, randomforest.cpp); запуск авторов без --use-reference-panels-in-EM. В статье механизма нет.

Замер: наклон в log–log

500100015002000110100N, людейчα = 2RFMixELAILoterLAMP-LD

α = log(T₂/T₁) / log(N₂/N₁)

500→10001000→2000
Loter0,740,96
ELAI0,860,98
RFMix2,102,72
T = a + bN + cN², a,b,c ≥ 0 ⇒ T(2N) ≤ 4T(N) ⇒ α ≤ 2.
RFMix: ×6,57 ⇒ α = 2,72. Даже N²·log(2N) даёт ≈ 2,1.
Лишний рост не объяснён.

Точки сняты с Fig. 2 (Schubert 2020), одна точка на размер; N < 500 сливаются. Пунктир — α = 2.

II. Память: пик, а не сумма

Сколько байт на один аллель

1 бит0,125uint81,0float648,0ELAI≈1,5RFMix11,5MOSAIC44LAMP-LD53Loter1660,1110100

s = (ΔMpeak/ΔN) / 2M

Информации в аллеле — 1 бит.

Loter хранит ≈ 166 Б:
вход 25 МБ → 33 ГБ.

Память задаёт представление данных, а не их объём.

Наклон по N = 500 и 2000 на Fig. 3; 2M = 10⁵ аллелей на человека. По коду Loter явные массивы 2N×M дают ≥ 49 Б; остальное не профилировано.

Хранить меньше: 149 МБ → 2,5 МБ

  1. стоимости нужен только предыдущий столбец
  2. путь из клетки ведёт либо в свою строку, либо в минимум — это 1 бит

R·M/8 + 4M ≈ 2,5 МБ (×59 меньше)

Операций столько же, но таблица влезает в L3.

сейчас 149 МБ 1 бит: 2,5 МБ L3 ≈ 30 МБ

Идея к EstimateSknn::s_cost_i; в Loter не реализовано, не измерено.

III. Масштабирование: пределы ускорения

Делим когорту на p частей

Три числа для любого метода

  1. α — как растёт время: замер на 3+ размерах, наклон в log–log
  2. Байт на аллель — сколько людей влезет: Nmax ≈ RAM / (2M·s)
  3. Единица деления — можно ли резать когорту и что станет с точностью
αБ/аллельточность
LAMP-LD≈ 0,753
ELAI1,0≈ 1,5
Loter1,0166ниже RFMix
MOSAIC—44
RFMix2,711,5лучшая медиана

α на 1000→2000. Не измерено в статье: несколько ядер, другие M и R, повторы, профиль.