windows deep internals: optimization of SASS stall counts
среда, 22 июля 2026 г.
optimization of SASS stall counts
Optimal instructions scheduling is NP-hard task. For this reason almost all compilers implement metaheuristic methods like list scheduling/Gibbons–Muchnick algorithm etc. ptxas is no exception - it also generates non-optimal scheduling, and this opens some opportunity for automatic optimization. Here I want to present scheduling model for SASS, tool for optimization of stall counts for binary CUBIN files, achieved results and possible direction for further improvements<br>First version
Has name dg.pl and used latency table extracted from ptxas with RE. Unfortunately it has at least 2 fatal flaws<br>This latency table is incomplete - for example some instructions like PRET/BFE/ICMP are missed. I tried to find similar table in more old ptxas versions - like 12, 11 and even 9 - it seems that they all incomplete<br>It takes into account only Read after Write joints and patched code crashed in random places, and on each launch in different places<br>After considerable and agonizing reflection, I concluded that it had used an incorrect model
so I decided to continue experiments with latency tables early extracted from nvdisasm<br>Latency tables
We can observe 3 types of tables in these files<br>TABLE_TRUE - it is quite obvious that this is Read after Write (RaW), row is write instruction, column is read. We can assume that this order is always the same - first instruction connecting by row and joint happens by column. Value is delay from Write till Read<br>TABLE_OUTPUT - both column and row contains Write operations - so this is Write after Write (WaW) joint. Surprise - seems that Write operations are asynchronous and must be separated from previous Write with some delay<br>and finally TABLE_ANTI - in this case row is Read and column is Write. So this is Write after Read (WaR) joint. It's still unclear if this table applies to different instructions or it also can be applied to the same like<br>@P0 ISETP P0
How expensive to track all this joints
I added to ead.pl some statistics how many columns and rows can a single instruction have. Results depend on SM version and are unexpected in some ways:<br>SM55 - avg 9.8 columns, 5 rows, HSETP2 has 17 (!) columns<br>SM70 - avg 5.6 columns, 4.3 rows, CSMTEST has 8 columns and rows
SM75 - avg 5.8 columns, 5.3 rows, PSETP has 9 rows<br>SM90 - avg 6 columns, 5.8 rows, R2UR has 11 columns
So on average for each instruction we must track 1 Write and 3-4 Reads. I keep them (see file nv_track.h) in std::pair - this is 12 bytes per record. All track records stored in std::list - so we have yet 2 pointers, total 28 bytes. Total size varies but in worst cases 15 (10 columns + 5 rows) * 28 = 420 bytes<br>Why this estimation is important? As you can see some tables while connecting require access to all encoded fields in their CONNECTOR CONDITIONS. So we have 2 variants<br>keep whole map of encoded fields and only 1 pointer to nv_instr for each instruction - then we could connect any joint at any moment<br>apply all connections for each instruction and keep only filtered by CONNECTOR CONDITIONS - then we could do their intersection on joint when it really happens
I chose the second option - connections are stored for every used register/predicate for each instruction in class reg_history and at joint I select only intersecting. Extracted fields have type std::unordered_map, number of fields usually > 10 so size of this object at least 240 bytes + some memory for unordered_map itself
dg2.pl
So I wrote tool to optimize stall counts taking into account all 3 type of joints. The main change from dg.pl is function traverse_lat - it first builds array @rl of redundant stall counts, then apply restrictions for WaW and WaR and tries to reduce stall counts after that<br>I am too lazy to keep exact values for WaW so I used dirty hack - I never patch instruction for second Write. The explanation is simple - if we reduce stall count for first Write then there is enough delay, and if not then ptxas already inserted this delay between them
Complexity of this construction is O(N * log(N)) - I visit every instruction and also check possible WaRs/WaWs with couple of lookups in map
Config file<br>Most of time we are not interested in optimization of whole program - we want to optimize only hot loops where kernel spent most of its execution time. I could automatically identify only most nested loops by detecting backedge, Unfortunately, to detect all loops I need to do some inter-block analysis and this is not simple task. So I just shifted this responsibility to the user - you can select only some functions and even peek ranges inside function via external config file
Format of config file is very simple (see function read_config):<br># this is comment<br># process whole body of SomeFunction<br>.text.SomeFunction<br># process loop in AnotherFunc from c0 till d40<br>.text.AnotherFunc c0-d40As you can see I use dirty hack - in CUBIN...