Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2000-11-30
2004-11-02
Donaghue, Larry D. (Department: 2154)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S127000, C718S104000
Reexamination Certificate
active
06813760
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer software and, more specifically, to methods for determining software performance on a multiple processor computer system.
BACKGROUND TO THE INVENTION
In today's world, the need for faster, more powerful computing platforms is increasing. One approach to meeting this need is the development of multiprocessing (parallel processing) systems. Multiprocessing systems are systems in which two or more processors work in parallel (at the same time). In theory, two processors can do twice as much work in the same amount of time as one processor. Assuming all processors are working fully in parallel, systems with N processors could do N times as much work as a system with only one processor in the same amount of time. As we will see, not all processors can run fully in parallel all the time.
One class of multiprocessing systems uses shared memory. Shared-memory is memory that is shared amongst all of the processors. Every processor can access any piece of data in shared memory.
Shared-memory multiprocessing systems have an inherent problem when two or more processors try to access the same memory at the same time. This type of event is known as a collision (or data contention). Allowing both processors to alter the same data may result in data corruption. Therefore, some method must be used to prevent data contention or to recover from it. Data contention is undesirable in a multiprocessing system, since there is overhead associated with handling each collision. This overhead prevents the system from reaching its full capacity.
Because of the problem of data contention, developers are continually seeking new ways to reduce such contention. Unfortunately, the amount of processing time wasted or lost due to collisions is difficult to find. There are many factors that affect software performance.
Of these factors, data contention in a computer with a shared memory architecture can constitute the largest contributor to execution time inefficiency.
For multiple processor systems capable of parallel processing, the data contention scheme can affect the processing time lost due to data contention. One scheme, used in Nortel Network's XA-Core shared memory multiprocessing engine for its DMS family of network switches, is termed a roll back scheme. This scheme is somewhat analogous to predictive branching used in modern multiple pipeline microprocessors. Simply put, the computer executes processes and if a process cannot commit or write its data to memory due to data contention, all the work performed for that process is discarded. In predictive branching, at a branch, the computer takes a chance and chooses a path in that branch. This branch is then executed in the background while the main program executes. Once the main program actually reaches the branch and takes a path, if the branch executed in the background corresponds to the path taken by the main program, then the data produced by the predictive branching is used. Otherwise, if the actual path taken is not the path executed predictively, then the data produced by the predictive branching is discarded. This means that the processing time used to execute the predictive branching is wasted.
If developers could find the probability of data contention and, hence, the probability of wasted processing time, this knowledge can be used advantageously to reduce such contention by either redesigning the software, rewriting the code, or redesigning the hardware.
SUMMARY OF THE INVENTION
The present invention provides methods which fulfill the above described need. Subroutines embedded in the software gather data during execution on a multiprocessor system with a shared resource. The data gathered relates to data contention (collisions) between processes in competing for the shared resource. Such data includes the number of collisions, the type of collisions, how much processing time is wasted by collisions, and how much processing time is used by successfully executed processes. After the data is gathered, this can be compiled and offloaded to a separate computer which calculates the software's performance relative to its shared resource.
In a first aspect the present invention provides a method of determining the performance of a computer program when the program is executed on a multiple processor computer system having a shared resource. The program produces multiple parallel processes which can be executed in parallel with all other processes and multiple serial processes which can execute in parallel only with parallel processes. The resource is shared between multiple processes such that the computer system implements a rollback scheme to arbitrate between processes which compete for access to said resource. The method comprises:
a) determining how many parallel processes complete their assigned tasks (Lp);
b) determining how many serial processes complete their assigned tasks (Ln);
c) determining how much processing time is used by parallel processes which complete their tasks (Up);
d) determining how much processing time is used by serial processes which complete their tasks (Un);
e) determining how may parallel processes have not been able to complete their tasks due to a first denial of access to the shared resource, said first denial of access being caused by a serial process (Rpn);
f) determining how many parallel processes have not been able to complete their tasks due to a second denial of access to the shared resource, said second denial of access being caused by another parallel process (Rpp);
g) determining how many serial processes have not been able to complete their tasks due to a third denial of access to the shared resource, said third denial of access being caused by a parallel process (Rnp);
h) determining how much processing time is spent by serial processes while waiting to finish its tasks, said waiting being caused by other serial processes finishing their tasks (W);
i) determining how much processing time is wasted by parallel processes which are not able to complete their tasks (COHp);
j) determining how much processing time is wasted by serial processes which are not able to complete their tasks (COHn); and
k) calculating a probability of a process not being able to complete its tasks due to competition for said resource, said probability being calculated using data gathered in steps a)-j),
wherein,
said rollback scheme comprises:
determining between two or more processes competing for access to said resource which process gains access to said resource; and
causing processes which have not been granted access to said resource to discard results which have been previously obtained by said processes which have not been granted access.
In a second aspect the present invention provides a method of determining the effect on program performance of resource access contention between processes produced by a computer program executed on a multiple processor computer system having a resource shared among said processes, said method comprising:
a) inserting multiple subroutines in said program, said substantive measuring data relating to the access of said processes to said resource and the effect of said resource to the execution time and number of said processes;
b) gathering said data measured by said subroutines; and
c) calculating a probability that contention between processes for said resource will result in wasted processing time, said probability being based on data gathered in step b).
REFERENCES:
patent: 5361352 (1994-11-01), Iwasawa et al.
patent: 5684947 (1997-11-01), Horie
patent: 6128708 (2000-10-01), Fitzpatrick et al.
patent: 6308316 (2001-10-01), Hashimoto et al.
patent: 6691303 (2004-02-01), Guthrie et al.
Sung Testing Shared Memory Parallel Programs IEEE 1998 pp. 539-566.
Drwiega Tadeusz J.
Fitzel Robert M.
Gauld James R.
Borden Ladner Gervais LLP
Donaghue Larry D.
Haszko Dennis R.
Nortel Networks Limited
LandOfFree
Method and a tool for estimating probability of data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and a tool for estimating probability of data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and a tool for estimating probability of data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3346554