| Analyzing diagnostic data generated by multiple threads within an instruction stream -> Monitor Keywords |
|
|
  Analyzing diagnostic data generated by multiple threads within an instruction streamUSPTO Application #: 20080098207Title: Analyzing diagnostic data generated by multiple threads within an instruction stream Abstract: A diagnostic method for outputting diagnostic data relating to processing of instruction streams stemming from a computer program, at least some of said instructions streams comprising multiple threads is disclosed. The method comprises the steps of: (i) receiving diagnostic data; (ii) reordering said received diagnostic data in dependence upon reordering data, said reordering data comprising data relating to said computer program; and (iii) outputting said reordered diagnostic data. In general, the instructions streams are processed by a plurality of processing units arranged to process at least some of said instructions in parallel, said diagnostic data being received from said plurality of processing units. (end of abstract) Agent: Nixon & Vanderhye, PC - Arlington, VA, US Inventors: Alastair David Reid, Simon Andrew Ford, Katherine Elizabeth Kneebone USPTO Applicaton #: 20080098207 - Class: 712227 (USPTO) The Patent Description & Claims data below is from USPTO Patent Application 20080098207. Brief Patent Description - Full Patent Description - Patent Application Claims
BACKGROUND OF THE INVENTION [0001]1. Field of the Invention [0002]The present invention relates to the field of data processing and in particular to diagnostic mechanisms for monitoring data processing operations. [0003]2. Description of the Prior Art [0004]Systems are being developed that have multiple processing units operable to process data in parallel. A compiler will compile a program to execute on a particular hardware system such that in a multi-processor system portions of the program will be sent to be executed by different processing units. Thus, much of the program will be executed in parallel and executing times and processing performance will be improved. However, a drawback of this is that the view of the program execution derived from diagnostic mechanisms such as debug are difficult for a programmer to understand and to relate back to the original sequential program. [0005]When an application has been split into multiple threads automatically, there are two conventional approaches to debugging the application. [0006]One can restrict the debug view at any time to only those parts which are equivalent to the original application. For example, if the program initializes a data-structure, then splits into four threads to modify the data structure, then waits for the four threads to complete, one can disallow observation on the data structure during the time that all four threads are modifying it because the state of the data structure will not reflect any valid state of the original unithreaded program. Clearly this has the disadvantage of not allowing diagnosis of a significant part of the program. [0007]Alternatively, one can allow the programmer to observe any operation at any point at the cost of requiring the programmer both to understand how the program was parallelized and to debug a multithreaded program (which is hard to do). [0008]In summary, when multiple processors are executing in parallel and independently producing traces of diagnostic information, it can be hard to understand the resulting traces independently of each other. This problem can be addressed by merging the data streams based on dependencies between the different streams using a topological sort. An example of this is shown in, D. Kimelman, D. Zernik, "On-the-fly topological sort-a basis for interactive debugging and live visualization of parallel programs", Workshop on Parallel & Distributed Debugging archive Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, San Diego, Calif., United States, pp. 12-20, 1993. While this approach does significantly simplify the event stream, it leaves a significant semantic gap between the program as written by the programmer and the program as executed on the multi-processor system. For example, if the original program requested execution of three tasks `T1`, `T2`, `T3` in order, a parallelizing compiler might detect that `T1` and `T2` must be executed in sequence but that `T3` may execute in parallel with `T1` and `T2` and it might decide to execute `T1` and `T2` on separate processors. If T1 and T2 are executed on separate processors, the compiler will insert synchronization or communication operations to ensure that the tasks execute in the required sequence. By tracing synchronization and communication operations, it is possible to recognise the dependency between these tasks. The topological sort would take into account the dependencies between `T1` and `T2` but, because there is no dependency between `T3` and the other two tasks, the traces produced could be any one of: a) T1 T2 T3b) T1 T3 T2c) T3 T1 T2and which of these three traces is produced may vary from one run of the program to another. This makes debugging the system harder because the programmer must disregard the order of some events (e.g., exactly when does T3 run) while paying careful attention to other events (e.g., that T1 and T2 execute in sequence). [0009]The problem identified above comes from the topological sort making sorting decisions based only on how the hardware runs the output of the transforming compiler. [0010]Embodiments of the present invention seek to use information about the original program and how it was parallelized to present the information in a way that relates to that original program. In this example, since the original program requested that the three tasks execute in order, embodiments of the invention will seek an event rearrangement of the actual trace to match that order. That is, it will only display the first trace (T1 T2 T3). The order of events will not depend on the actual execution order. [0011]Furthermore, diagnosis can be difficult when an application has been written as a number of separate threads or even as a number of separate programs or where it is not possible to modify the part of the compiler that automatically parallelizes the program. There are three conventional approaches to understanding execution in these cases. [0012]One can observe the operations as a single sequential trace. Having a single trace is, in some sense simple but the trace is hard to understand because of the interleaving of multiple independent operations which requires the programmer to keep many things in their head at once. [0013]One can split the trace into a number of separate threads according to which thread/processor executes each operation. This is complicated as it requires the programmer to reason carefully about the communication protocol used between the different threads. [0014]One can split the trace into sequences of causally related operations using statistical means as was done by, for example, Aguilera et al., "Performance debugging for distributed systems of black boxes", Proceedings of the nineteenth ACM symposium on Operating systems principles, ACM Press, pp 74-89, 2003. This can help program understanding but not debugging because it can only display a subset of the trace (those sequences whose probability of being causally related is high) and because even though a sequence is probably correct, it may still be wrong so there is a possibility of confusion. Furthermore, because of its statistical nature, long sequences of operations are hard to construct because it takes a lot of observations before one can be confident that a sequence of 100 fairly probable events is itself fairly probable. [0015]Lamport's work "Time Clocks and Ordering of Events in a Distributed System" communications of the ACM 21, 7 (July 1978) pp 558-565. on sequential consistency and clocks proposes the "happens before" partial order and suggests extending it to an arbitrary total order in order to implement a mutual exclusion protocol. It does not suggest use in debugging. [0016]It would be desirable to be able to analyse an execution trace of a program having multiple threads in a similar manner to the analysis that can be performed for a trace of a sequential program run on a single processor. SUMMARY OF THE INVENTION [0017]A first aspect of the present invention provides a diagnostic method for outputting diagnostic data relating to processing of instruction streams stemming from a computer program, at least some of said instructions streams comprising multiple threads, said method comprising the steps of: (i) receiving diagnostic data;(ii) reordering at least one received diagnostic data item from said received diagnostic data with respect to at least one other received diagnostic data item in dependence upon reordering data, said reordering data comprising data relating to said computer program; and(iii) outputting said reordered diagnostic data. [0018]In order to address the problem of a computer program that is divided into a plurality of threads, being hard to analyse when it is being processed, the present invention analyses any diagnostic data generated in conjunction with data relating to the original written computer program. It uses the information from the original written computer program as reordering data to help in reordering the received diagnostic data and it is this reordered diagnostic data that is then analysed. Thus, the diagnostic data received can be reordered into a form that more closely matches the original computer program and thus is easier for a programmer to understand and analyse. It should be noted that a computer program may be divided in to a plurality of threads prior to execution when it is to be executed on multiple processing or execution units in parallel, or it may be so divided by a compiler in the expectation that the program will run on such a platform, although the execution is actually performed by a single processor. [0019]In some embodiments said diagnostic method comprising a further step: (iia) removing at least one received diagnostic data item from said received diagnostic data in dependence upon said reordering data. [0020]In other embodiments said diagnostic method comprising a further step: (iib) merging at least one received diagnostic data item from said received diagnostic data with at least one other received diagnostic data item in dependence upon said reordering data. Continue reading... Full patent description for Analyzing diagnostic data generated by multiple threads within an instruction stream Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Analyzing diagnostic data generated by multiple threads within an instruction stream patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Analyzing diagnostic data generated by multiple threads within an instruction stream or other areas of interest. ### Previous Patent Application: Plotting device and plotting method Next Patent Application: Analyzing and transforming a computer program for executing on asymmetric multiprocessing systems Industry Class: Electrical computers and digital processing systems: processing architectures and instruction processing (e.g., processors) ### FreshPatents.com Support Thank you for viewing the Analyzing diagnostic data generated by multiple threads within an instruction stream patent info. IP-related news and info Results in 1.26071 seconds Other interesting Feshpatents.com categories: Software: Finance , AI , Databases , Development , Document , Navigation , Error |
||
