Resource conflict resolution algorithms

This chapter describes algorithms for resource conflict resolution. Resource conflicts occur when multiple operations activate the same hardware resource simultaneously. When all operations in the hardware model have fixed execution delays, conflict resolution becomes part of the scheduling and resource binding tasks. In particular, operations scheduled to different control stq)s or belonging to mutually exclusive conditional branches can share their hardware resources. Consider for example the force-directed scheduling technique [PK89b]. Operations with similar resources are first scheduled to reduce their concurrency, then they are bound to hardware resources subject to this schedule. The binding step ensures that no resource conflicts will arise. This approach is, however, restricted to bounded delay operations. 

Organization of chapter. This chapter presents the formulation and algorithms for relative scheduling. Our approach can be described in a nutshell as follows. In relative scheduling, we support both operations with fixed delay and operations with data-dependent delay data-dependent delay operations represent points of synchronization. We uniformly model both types of operations as vertices in the constraint graph model. We assume in this cluq)ter that resource binding and conflict resolution have been performed prior to scheduling. 

Algorithms for conflict resolution is presented in this section. The input is a resource binding consisting of a number of instance operation sets. The instance op tion sets in / are selected in turn. For a given instance operation set O, its operation clusters are first identified using standard graph techniques... 

This section presented algorithms to resolves the conflicts that arise when multiple operations share the same hardware resource. In traditional synthesis approaches that consider only operations with bounded execution delays, conflict resolution is defined as part of the scheduling and resource binding tasks. These approaches are inappropriate for the sequoicing graph model because of its support for data-dependent delay opmtions. 

---