@article{baev_meleis_eichenberger_2002, title={An experimental study of algorithms for weighted completion time scheduling}, volume={33}, ISSN={["0178-4617"]}, DOI={10.1007/s00453-001-0103-x}, number={1}, journal={ALGORITHMICA}, author={Baev, ID and Meleis, WM and Eichenberger, A}, year={2002}, month={May}, pages={34–51} }
 @article{baev_meleis_eichenberger_2002, title={Lower bounds on precedence-constrained scheduling for parallel processors}, volume={83}, ISSN={["1872-6119"]}, DOI={10.1016/S0020-0190(01)00303-9}, abstractNote={We consider two general precedence-constrained scheduling problems that have wide applicability in the areas of parallel processing, high performance compiling, and digital system synthesis. These problems are intractable so it is important to be able to compute tight bounds on their solutions. A tight lower bound on makespan scheduling can be obtained by replacing precedence constraints with release and due dates, giving a problem that can be efficiently solved. We demonstrate that recursively applying this approach yields a bound that is provably tighter than other known bounds, and experimentally shown to achieve the optimal value at least 90.3% of the time over a synthetic benchmark. We compute the best known lower bound on weighted completion time scheduling by applying the recent discovery of a new algorithm for solving a related scheduling problem. Experiments show that this bound significantly outperforms the linear programming-based bound. We have therefore demonstrated that combinatorial algorithms can be a valuable alternative to linear programming for computing tight bounds on large scheduling problems.}, number={1}, journal={INFORMATION PROCESSING LETTERS}, author={Baev, ID and Meleis, WM and Eichenberger, A}, year={2002}, month={Jul}, pages={27–32} }
 @article{meleis_eichenberger_baev_2001, title={Scheduling superblocks with bound-based branch trade-offs}, volume={50}, DOI={10.1109/12.946999}, abstractNote={Since instruction level parallelism in basic blocks is often limited, compilers increase performance by creating superblocks that allow operations to be issued speculatively. This is difficult in general because each branch competes for the processor's limited resources. Previous work manages the performance trade-offs that exist between branches only indirectly. We show here that dependence and resource constraints can be used to gather explicit knowledge about scheduling trade-offs between branches. This paper's first contribution is a set of new, tighter lower bounds on the execution times of superblocks that specifically account for the dependence and resource conflicts between pairs of branches. This paper's second contribution is a novel superblock scheduling heuristic that finds high performance schedules by determining the operations that each branch needs to be scheduled early and selecting branches with compatible needs that favor beneficial branch trade-offs. Performance evaluations for superblocks from SPECint95 indicate that our bounds are very tight and that our scheduling heuristic outperforms well-known superblock scheduling algorithms.}, number={8}, journal={IEEE Transactions on Computers}, author={Meleis, W. M. and Eichenberger, A. E. and Baev, I. D.}, year={2001}, pages={784–797} }
 @article{eichenberger_davidson_1997, title={Efficient formulation for optimal module schedulers}, volume={32}, ISSN={["0362-1340"]}, DOI={10.1145/258916.258933}, abstractNote={Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. In this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. For example, the total execution time is reduced by a factor of 8.6 when 782 loops from the Perfect Club, SPEC, and Livermore Fortran Kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. Experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.}, number={5}, journal={ACM SIGPLAN NOTICES}, author={Eichenberger, AE and Davidson, ES}, year={1997}, month={May}, pages={194–205} }