Interesuje mnie wczesna historia opublikowanych wyników dotyczących kompromisów czasoprzestrzennych ogólnego przeznaczenia. W szczególności chcę wiedzieć, kto jako pierwszy opisał następujący typ algorytmu do oceny obliczeń posiadających dowolny wykres przepływu danych z O-stopniem (1), wykorzystujący przestrzeń proporcjonalną do głębokości (nie szerokości) wykresu przepływu danych (plus rozmiar danych wejściowych), wykonując prostą pierwszą ocenę głębokości wykresu. Bardziej szczegółowo:
Niech wykres przepływu danych będzie G = (V, E), gdzie V jest zbiorem wierzchołków obliczeniowych (wartości danych wielkości O (1)), a E jest zbiorem krawędzi (v_p, v_s), tak że wartość następcy wierzchołek v_s \ in V zależy natychmiast od wartości poprzednika wierzchołek v_p \ in V. Niech v_f będzie wierzchołkiem bez następców reprezentujących końcowy wynik obliczeń. Niech będę kanonicznie uporządkowanym zestawem wierzchołków wejściowych (bez poprzedników), dla i \ in I podano jego wartość x (i). Dla innych wierzchołków v \ in S ich wartości są zdefiniowane przez x (v) = F_v (x (P (v))), gdzie P (v) jest uporządkowaną kanonicznie listą poprzedników v, x (P (v)) to odpowiednią listę ich wartości, a F_v jest funkcją wierzchołka, która określa jej wartość jako funkcję listy wartości swoich poprzedników.
Biorąc pod uwagę tę konfigurację, omawiany algorytm jest dość oczywisty i trywialny:
def eval(v): (v can be any vertex in the graph)
let P := P(v), the list of v's predecessors (has O(1) elements by assumption)
let val[] := uninitialized array of |P| data values
for each predecessor p[i] in P (i.e. for i from 1 to |P|):
if p[i] is in I then
val[i] = x(p) (look up a given input)
else
val[i] = eval(p[i]) (recursive call)
return F_v(val[]) (apply vertex's function to list of predecessor values)
Wymaga to O (d) poziomów rekurencji, gdzie d jest głębokością wykresu przepływu danych, a przestrzeń stosu na każdym poziomie jest stała ze względu na założenia, że stopień wykresu przepływu danych jest stały i że rozmiar wartości danych są stałe. (Dla uproszczenia traktuję również wielkość odniesień wierzchołków jako stałą, nawet jeśli są one naprawdę logarytmiczne w | V |.). Zatem całkowite wykorzystanie przestrzeni wynosi O (d + | I |). Maksymalna szerokość wykresu przepływu danych może być wykładniczo większa niż ta, więc w najlepszym przypadku ta technika może zapewnić dość ekstremalne oszczędności miejsca, w porównaniu do, powiedzmy, zachłannej oceny wykresu z wyprzedzeniem (co może być przy każdym krok, oceń wszystkie wierzchołki, które bezpośrednio zależą tylko od wierzchołków, których wartości są już znane,
W każdym razie jest to dość oczywista technika, przynajmniej z perspektywy czasu, i z pewnością jest znana od dawna, ale zastanawiałem się, jak cofnęła się literatura na jej temat. Ktoś zna wczesną historię wyników tego rodzaju (opisywanych w tych terminach lub innych analogicznych) i co byłoby dobrym odniesieniem do wnikania w ten temat?
Dziękuję bardzo, Mike Frank
źródło