Abstract
Compiler optimization and transformation techniques focus on eliminating branches from the instruction stream and overlapping the execution of multiple control flow paths using the conditional execution capabilities provided by predication. The compiler support for predicate[1] execution is based on hyperblock, which is a generalized form of superblock that takes advantage of both predicated and speculative execution. The paper discusses the compilation techniques of hyperblock. The algorithm works well for inner most loops. However, for general acyclic code, external boundaries do not exist. As a result, the hyperblocks tend to grow along particular paths of control. New technique (PHG is used) to form efficient hyperblocks in acyclic code will increase the effectiveness of hyperblock techniques across all the bench marks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Verma, S., Biswas, R., Singh, J.B.: Modified Architectural Support for predicate execution of Instruction level parallelism. International Journal of Computer and Electrical Engineering, IJCEE (April 2010)
Aho, V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools. Addison-Wesley Publishing Company, Reading (1986)
Colwell, R.P., et al.: A VLIW Architecture for a Trace Scheduling Compiler. IEEE trans. on Computers (August 1988)
Rajagopalan, S., Rajan, S.P., Malik, S., Rigo, S., Araujo, G., Takayama, K.: A Ratargetable VLIW Compiler.Framework for DSP with Instruction Level Parallelism. IEEE Transactions on Computer –Aided Design Of Integrated Circuits and Systems 20(11) (November 2001)
Chen, P.-S., Hwang, Y.-S., Ju, R.D.-C., Lee, J.K.: Interprocedural Probabilistic Pointer Analysis. IEEE Transaction on Parallel and Distributed Systems 15(10) (October 2004)
Connors, D.A., August, D.I., Crozier, K.M., Hwu, W.W., Puiatti, J.-M.: An Architecture Framework for Introducing Predicated Execution into EmbeddedMicroprocessors
Anantaraman, A., Seth, K., Patil, K., Rotenberg, E., Mueller, F.: Virtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems. In: Proceedings of the international symposium on computer architecture (June 2003)
Berg, C., Engblom, J., Wilhelm, R.: Requirements for and design of a processor with predictable timing. In: Proceedings of the dagstuhl perspectives workshop on design of systems with predictable behavior (2004)
Deverge, J., Puaut, I.: Safe measurement-based WCET estimation. In: Proceedings of the Euromicro international workshop on WCET analysis (2005)
Fisher, J.A., Faraboschi, P., Young, C.: Embedded computing: a VLIW approach to architecture, compilers, and tools. Kaufmann, Los Altos (2005)
Cvetanovic, Kessler: Performance analysis of the Alpha 21264-based Compaq ES40 system. In: Notes on Proceedings of the 27th ACM International Symposium on Computer Architecture, Vancouver, Canada (2000)
Kunle, Basem, Lance, Ken, Kunyung: The Case for a Single-Chip Multiprocessor, pp. 1–2. Computer Systems Laboratory Stanford University
Lipasti, M.H., Shen, J.P.: Exceeding the Dataflow Limit via Value Prediction, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213
Fisher, J.A., Freudenberger, S.M.: Predicting Conditional Branch Directions. From Previous Runs of a Program, pp. 85–87
Monchiero, M., Palermo, G., di Milano, P.: The Combined Perceptron Branch Predictor. Dipartimento di Elettronica e Informazione Via Ponzio, Milan, Italy fmonchier, Report 04, vol. 34/5, 20133, 1–2
Steven, Luke, Swift, Susan, Henry: An Evaluation of Speculative Instruction Execution on Simultaneous Multithreaded Processors. Levy University of Washington, 1–3
Scott-, Combining Branch Predictor. Technical Report. Technical Note TN-36, Digital Equipment Corporation, Western Research Lab. (June 1993)
Yeh, T.Y., Patt, Y.N.: A comparison of dynamic branch predictors that use two levels of branch history. In: Proceedings of 20th annual International Symposium. On Computer Architecture, May 1993, pp. 257–266. IEEE and ACM (1993)
Hideki, C., Tetsuya, M.: Unconstrained Speculative Execution with Predicated State Buffering. System LSI Laboratory Mitsubishi Electric Corporation 4-1, Mizuhara, Itami, Hyogo, Japan, 664, pp. 126–127
Ofri: Inside Intel’s Core Micro architecture. Setting New Standards for Energy-Efficient Performance. Ofri Wechsler Intel Fellow, Mobility Croup Director, Mobility Microprocessor Architecture Intel Corporation White Paper 06
Packard, H.: Characterizing x86 processors for industry-standard servers: AMD Opteron and Intel Xeon Whitepaper, technology brief, 2nd Edn. Hewlet Packard (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Verma, S., Biswas, R., Singh, J.B. (2010). Extension of Superblock Technique to Hyperblock Using Predicate Hierarchy Graph. In: Ranka, S., et al. Contemporary Computing. IC3 2010. Communications in Computer and Information Science, vol 95. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14825-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-14825-5_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14824-8
Online ISBN: 978-3-642-14825-5
eBook Packages: Computer ScienceComputer Science (R0)