Triangularization: A Two-Processor Scheduling Problem

摘要

The authors explore the following matrix problem: Given an nxn boolean matrix, isthere a permutation of the rows and a permutation of the columns such that the resulting matrix is lower triangular. They show the relationship of this matrix problem to the two important scheduling problems: optimization of code for pipelined execution and microcode compaction for very long instruction computers.