Enhanced Co-Scheduling: A Software Pipelining Method Using Modulo-Scheduled Pipeline Theory

Govindarajan, R.; Rao, N. S. S. Narasimha; Altman, E. R.; Gao, Guang R.
February 2000
International Journal of Parallel Programming;Feb2000, Vol. 28 Issue 1, p1
Academic Journal
Instruction scheduling methods which use the concepts developed by the classical pipeline theory have been proposed for architectures involving deeply pipelined function units. These methods rely on the construction of state diagrams (or automatons) to (i) efficiently represent the complex resource usage pattern; and (ii) analyze legal initiation sequences, i.e., those which do not cause a structural hazard. In this paper, we propose a state-diagram based approach for modulo scheduling or software pipelining, an instruction scheduling method for loops. Our approach adapts the classical pipeline theory for modulo scheduling, and, hence, the resulting theory is called Modulo-Scheduled pipeline (MS-pipeline) theory. The state diagram, called the Modulo-Scheduled (MS) state diagram is helpful in identifying legal initiation or latency sequences, that improve the number of instructions initiated in a pipeline. An efficient method, called Co-scheduling, which uses the legal initiation sequences as guidelines for constructing software pipelined schedules has been proposed in this paper. However, the complexity of the constructed MS-state diagram limits the usefulness of our Co-scheduling method. Further analysis of the MS-pipeline theory, reveals that the space complexity of the MS-state diagram can be significantly reduced by identifying primary paths. We develop the underlying theory to establish that the reduced MS-state diagram consisting only of primary paths is complete; i.e., it retains all the useful information represented by the original state diagram as far as scheduling of operations is concerned. Our experiments show that the number of paths in the reduced state diagram is significantly lower—by 1 to 3 orders of magnitude—compared to the number of paths in the original state diagram. The reduction in the state diagram facilitate the Co-scheduling method to consider multiple initiations sequences, and hence obtain more efficient schedules. We call the resulting method, enhanced Co-scheduling. The enhanced Co-scheduling method produced efficient schedules when tested on a set of 1153 benchmark loops. Further the schedules produced by this method are significantly better than those produced by Huff's Slack Scheduling method, a competitive software pipelining method, in terms of both the initiation interval of the schedules and the time taken to construct them.


Related Articles

  • The Cell Broadband Engine: Exploiting Multiple Levels of Parallelism in a Chip Multiprocessor. Gschwind, Michael // International Journal of Parallel Programming;Jun2007, Vol. 35 Issue 3, p233 

    As CMOS feature sizes continue to shrink and traditional microarchitectural methods for delivering high performance (e.g., deep pipelining) become too expensive and power-hungry, chip multiprocessors (CMPs) become an exciting new direction by which system designers can deliver increased...

  • Evaluating Architectures for Intelligence. Kaminka, Gal A.; Burghart, Catherina R. // AI Magazine;Winter2007, Vol. 28 Issue 4, p120 

    The article takes a look on the assessment of the architectures for intelligence. According to the authors, architectures form an integral part of artificially intelligent agents and robots. It stresses that architectures structure and organize the knowledge used by the agents to select actions...

  • The Future of Computer Science. Hopcroft, John E.; Soundarajan, Sucheta; Liaoruo Wang // International Journal of Software & Informatics;Dec2011, Vol. 5 Issue 4, p549 

    Computer science is undergoing a fundamental change and is reshaping our understanding of the world. An important aspect of this change is the theory and applications dealing with the gathering and analyzing of large real-world data sets. In this paper, we introduce four research projects in...

  • Domain science and engineering from computer science to the sciences of informatics. Part II: science. Bjørner, D. // Cybernetics & Systems Analysis;Mar2011, Vol. 47 Issue 2, p260 

    We discuss means for describing domains. We do so on the background of the example of part I of the present (Part II) paper and in its discussion. The discussion amounts to a proposal for a base description ontology. The discussion borders between computer science and an emerging Philosophy of...

  • Retargeting Sequential Image-Processing Programs for Data Parallel Execution. Baumstark, Jr., Lewis B.; Wills, Linda M. // IEEE Transactions on Software Engineering;Feb2005, Vol. 31 Issue 2, p116 

    New compact, low-power implementation technologies for processors and imaging arrays can enable a new generation of portable video products. However, software compatibility with large bodies of existing applications written in C prevents more efficient, higher performance data parallel...

  • Formal Specification and Analysis of Software Architectures Using the Chemical Abstract Machine Model. Inverardi, Paola; Wolf, Alexander L. // IEEE Transactions on Software Engineering;Apr95, Vol. 21 Issue 4, p373 

    We are exploring an approach to formally specifying and analyzing software architectures that is based on viewing software systems as chemicals whose reactions are controlled by explicitly stated rules. This powerful metaphor was devised in the domain of theoretical computer science by...

  • Developing, and testing, a theoretical framework for inter-organisational systems (IOS) as infrastructure to aid future IOS design. Borman, Mark // Information Systems & e-Business Management;Oct2006, Vol. 4 Issue 4, p343 

    Over time many inter-organisational systems (IOS) have evolved to become open systems with the promise of delivering benefits to their broad base of organisational users. However in practice benefits have often remained concentrated, primarily accruing to the dominant party, resulting in low...

  • Exchange Upgrade Can Be a Tough Haul. Connolly, P. J. // InfoWorld;10/13/2003, Vol. 25 Issue 40, p30 

    Deals with the difficulties faced in upgrading the Exchange e-mail server platform from Microsoft. Service adapted by Windows NT; Factors that made customers decide to stick with Exchange 5.x installations; Importance of e-mail systems to corporate life. INSETS: Exchange Server 2003;Migrating...

  • Software Systems’ Intra/Inter-Anticipation. Torres-Carbonell, J. J.; Paderewski-Rodríguez, P.; Parets-Llorca, J. // AIP Conference Proceedings;2004, Vol. 718 Issue 1, p406 

    Software Systems are complex entities composed by elements or components, subsystems, interrelated that could be considered themselves as systems. The evolution and functioning of the system as a whole is to be thought out as an anticipatory process. Additionally, the subsystems are also to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics