Dynamic Speculation and Synchronization of Data Dependences Andreas Moshovos Scott E Breach T N Vijaykumar Gurindar S Sohi Computer Sciences Department University of Wisconsin Madison 1210 West Dayton St Madison WI 53706 moshovos breach vijay sohi cs wisc edu Abstract Data dependence speculation is used in instruction level parallel ILP processors to allow early execution of an instruction before a logically preceding instruction on which it may be data dependent If the instruction is independent data dependence speculation succeeds if not it fails and the two instructions must be synchronized The modern dynamically scheduled processors that use data dependence speculation do so blindly i e every load instruction with unresolved dependences is speculated In this papen we demonstrate that as dynamic instruction windows get large significant performance benefits can result when intelligent decisions about data dependence speculation are made We propose dynamic data dependence speculation techniques i to predict tf the execution of an instruction is likely to result in a data dependence mis specularion and ii to provide the synchronization needed to avoid a mis speculation Experimental results evaluating the effectiveness of the proposed techniques are presented within the context of a Multiscalarprocesson 1 Introduction Speculative execution is an integral part of modem ILP processors be they statically or dynamically scheduled designs Specu lation may take two forms control speculation and data speculation Control speculation implies the execution of an instruction before the execution of a preceding instruction on which it is control dependent Data speculation implies the execution of an instruction before the execution of a preceding instruction on which it may be or is data dependent To date much attention has been focused on control speculation This outlook is natural because control speculation is the first step Control speculation or some equivalent basic block enlargement technique such as if conversion with predicated execution is required if we want to consider instructions from more than one basic block for possible issue Given the sizes of basic blocks the need to go beyond a basic block became apparent some time ago and several techniques to permit control speculation were developed both in the context of statically and dynamically scheduled machine models Improving the accuracy of control speculation especially dynamic techniques via the use of better branch prediction has been the subject of intensive research recently a plethora of papers on dynamic and static branch prediction techniques havebeenpublished Data speculation has not received as much attention as control speculation The two forms of data speculation that have received some attention are data speculation and data denendence Permission personal to make digital hard or classroom copy of pars or all this work for use is granted copies are not made or distributed tage the copyright notice without for profit fee provided or the title of the publication redistribute 0 97 1997 to lists requires Denver ACM prior specific permission CO USA advan and its date appear and notice is given that copying is by permission Inc To copy otherwise to republish to post on servers ISCA that commercial of ACM or to and or a fee speculation In data value speculation an attempt is made to predict the data value that an instruction is going to produce 15 19 In data dependence speculation no explicit attempt is made to predict data values Instead a prediction is made on whether the input data value of an instruction has been generated and stored in the corresponding named location memory or register Most of the research on data dependence speculation has focused on ensuring correct execution while carrying out this form of speculation 8 9 10 18 and on static dependence analysis techniques 1 2 5 6 21 So far no attention has been given to dynamic techniques to improve the accuracy of data dependence speculation This is because in the small instruction window sizes of modem dynamically scheduled processors 12 11 14 the probability of a r speculation is small and furthermore the net performance loss that is due to erroneous data dependence speculation is small In this paper we argue that as dynamically scheduled ILP processors are able to establish wider instruction windows the net performance loss due to erroneous speculation can become significant Accordingly we are concerned with dynamic techniques for improving the accuracy of data dependence speculation while maintaining the performance benefits of aggressive speculation We propose techniques that attempt i to predict those instructions whose immediate execution is going to violate a true data dependence and ii to delay the execution of those instructions only as long as is necessary to avoid the r speculation A preliminary evaluation of the ideas presented in this paper was first reported in 171 The rest of this paper is organized as follows First in section 2 we review data dependence speculation and discuss how it affects IL P execution Then in section 3 we discuss the components of a method for accurate and aggressive memory data dependence speculation while in section 4 we present an implementation framework for this method In section 5 we provide experimental data on the dynamic behavior of memory dependences and present an evaluation of an implementation of the method we propose within the context of a Multiscalar processor 3 4 7 20 Finally in section 6 we list what in our opinion are the contributions of this work and offer concluding remarks In the discussion that follows we are concerned with data dependence speculation accordingly we use the terms data dependence speculation data speculation and speculation interchangeably 2 Data Dependence Speculation Programs are written with an implied executes data values are produced and tions These values are conveyed from sumer by binding the value to a named registers and memory An ILP or other parallel machine takes a suitable subset of the instructions an instruction window of a program and converts the total order within this subset into a partial order This is done so that instructions may execute in parallel and or in an execution order that might be different from the total order The shape of the 0 89791 901 7 97 0006 3 50 181 I total order As a program consumed by its instructhe producer to the constorage location
View Full Document
Unlocking...