protocol_cost_models
The physical cost model prices the levels of the formatted tensors of a program, as StorageBasis does, and the accesses of them at the loops of each query, as ProtocolBasis does, each kind of level differently, so that the protocol optimizer can choose the protocol of each read, and the formatter the kind of each level.
AccessBasis
¶
Bases: Basis[ProtocolChoice], LoopOrderedForm
A basis whose components are the accesses of the levels of the formatted tensors at the last loop of each loop prefix, each a row of FEATURES. The loops within a loop are entered where the formats say, whatever the protocols at it, so the protocols at a loop only change its own rows, and choose_protocols picks each loop on its own.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 | |
DenseLevelOption
¶
Bases: LevelOption
Storage features are positions and slots.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
ElementLevelOption
¶
Bases: LevelOption
The element level at the rank of a tensor stores one value for each position. Storage features are values and value bytes.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
LevelBasis
¶
Bases: Basis[ProtocolChoice], LoopOrderedForm
A basis whose components are the accesses, as AccessBasis lists them, and whose rows are the storage features of option at the accesses which write a level of it: the level stores what the query writes, as written gives it, entered at the fibers the access enters. The tensors a query reads are already stored, so a read costs no storage.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
LevelOption
¶
Bases: ABC
A kind of level, which gives the storage features feature_names names, and the positions it passes to its child, from the stats of the tensor, the zero-based depth of the level, and the num_pos positions entering it. A tensor which stores one slice that fixes the fields of over is described by its largest slice. A level which filters has a fiber only where it has an entry, so a lookup which finds none runs nothing within it.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
ProtocolBasis
¶
Bases: ByKind[ProtocolChoice, str]
The accesses of the levels of each formatted tensor, each under the basis of the kind of its level and, within it, of its protocol, so that a linear model prices each feature of an access by both.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
ProtocolChoice
dataclass
¶
An access of the level of a tensor at a zero-based stored depth by a query, at the last loop of prefix, which reaches the level: the last loop over a field of the levels from the root to it, or, for the element level at the rank of the tensor, to the last of them. table is the read, in the expression of prefix, or, if write, the table of the output of the query, and options are the kinds of the levels of the tensor, outermost first.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
SparseByteMapLevelOption
¶
Bases: LevelOption
A bytemap flags each of its slots with a byte, and lists the slots which are occupied, so its children are allocated densely. Storage features are positions, slots, entries, and the bytes of its pointers and list.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
SparseHashLevelOption
¶
Bases: LevelOption
Storage features are positions, entries, position bytes, and index bytes.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
SparseListLevelOption
¶
Bases: LevelOption
Storage features are positions, entries, position bytes, and index bytes.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
StorageBasis
¶
Bases: ByKind[ProtocolChoice, str]
The storage of the levels each access writes, each under the basis of the kind of its level.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
accesses(term, bindings, machine)
¶
The accesses of the levels of the formatted tensors of bindings at the last loop of each loop prefix of term, advancing machine past each query.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
allowed_options(alias, depth, term, options)
¶
The options which can take the level of alias at a depth in term: those which support the protocols term reads and writes it with.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
level_accesses(prefix, formats)
¶
The reads of levels at the last loop of prefix, then the writes of the levels of its output, if formats lists the options of its levels, with the write of its element level where the last of them is reached.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
level_formats(bindings)
¶
The options of the levels each alias of bindings stores, outermost first and ending with its element level, as the bases of formatted programs take them. A binding is either such a list, or a format, whose options level_options lists. An alias whose format stores a level of no option is left out.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
level_options(fmt)
¶
The options of the levels which a fiber tensor of the format fmt stores, outermost first and without its element level, or None where fmt isn't a fiber tensor or stores a level of no option.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
level_reads(prefix, formats)
¶
The levels which the tables of the query of prefix read at its last loop: those of the tensors of formats, whose options list the levels each alias stores, outermost first. A table which occurs several times reads each level once.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
nnz_after(stats, stats_factory, depth, over=())
¶
Return the non-fill entries of the first depth + 1 levels of stats, in the largest slice which fixes the fields of over.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
parents(access, spaces)
¶
The fibers of the level an access enters: those at the positions the enclosing loops reach, or, where a level above is reached at this loop, those it visits.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
protocol_names(option)
¶
The protocols a level of option is accessed with, once chosen.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
reached_depths(loops, idxs, nfused)
¶
The zero-based stored depths of the levels of a table of idxs, whose first nfused fields are fused, which are reached at the last of loops: those whose fields, and the fields of the levels above them, are all looped over by then, the last of them there.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
read_options(option, idxs, nfused, depth, loop_order)
¶
The protocols which a table of idxs, whose first nfused fields are fused, can read a level of option at a zero-based stored depth with under loop_order. A walk or a gallop steps through the level at the loop over its field, so that loop must come after the loops over the fields of the levels above it. Otherwise the level is reached inside the loop over its field, where it can only be followed.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
read_protocols(alias, depth, term)
¶
The protocols which term reads the level of alias at a depth with. A read which gives no protocol takes whichever the level supports, which the protocol optimizer chooses, so it constrains nothing.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
rescans_a_root(loops, reads, protocols)
¶
Whether reading reads with protocols at the last of loops, within the others, steps through the root level of a table, such as a vector, which has the same entries at every execution of the loop, where a sparse level of another read, whose fiber the enclosing loops choose, could lead the loop instead. A walk steps through the root again at every execution, and so does a gallop of it beside a walk, which ends no phase, or beside no other gallop; a gallop leapfrogging with that of another read doesn't. The length of the root is exact while DC stats bound the other fibers by the largest, so the model may price stepping through it below following it, which looks up only where the others lead. Reads whose protocols the program gives are not among reads.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
write_protocols(alias, depth, term)
¶
The protocols which term writes the level of alias at a zero-based stored depth with, as util.write_protocols infers them under the loops of the enclosing Fuse nodes. An update which reduces into alias laminates what it already stores, but one which overwrites it or sets it to a literal starts it again.
Source code in src/finch/autoschedule/cost_models/protocol_cost_models.py
written(prefix, machine)
¶
The stats of where the query of prefix writes its output: those of its expression, with each table whose levels from the last which filters down don't filter spanning their fields wholly, as the formats of prefix give them. A read of such a level finds a value at every slot, so the query writes wherever it reads one, whatever the value.