CSCI 693 Research Paper: BOYCHUCK, DavidABSTRACTAs CPU architectures are exploiting thread level parallelism more effectively, we see the number of multi-threaded applications increasing. It is important to ensure that we are using the best thread architectures. This paper presents two programs that are recursive in nature and are built on two different thread architectures; on-the-fly thread creation, and a thread pool, and compares the programs against each other. We find that a thread pool outperforms on-the-fly thread creation in nearly every category examined. We conclude by examining the data’s implications on program optimality.INTRODUCTIONRecursive programming in its own right can be difficult to analyze for efficiency. By adding a threaded programming model where threads are created recursively, the task of analyzing performance metrics becomes exponentially more difficult. However, careful analysis of program behavior is the key to understanding how recursively threaded programs operate in a dynamic environment. Only after careful analysis of different threaded program architectures can one begin to see the benefits or weaknesses between them. To gather the required information there must be a way to benchmark program behavior and gather data from different program architectures when they are run with the same arguments in the same system environment.1Analysis of Recursively ThreadedProgramming ArchitecturesDavid BOYCHUCKD. Boychuck is a MS candidate in computer science at California State University, Chico, CA 95929-0410 USA (e-mail: [email protected])CSCI 693 Research Paper: BOYCHUCK, DavidThere are several important issues to consider when performing this type of program benchmarking. First and foremost, any differences in program architectures must be identified as to account for any types of discrepancy when collecting data. Second, it is important to be able to extract data relevant to program behavior. In our work we present two recursive threaded programming architectures and give the required technical background to enable complete understanding of analysis and results. We then give our methodology and explain the environment that the analysis and benchmarking will take place in. Next we present the results of our experimentation and finally draw conclusions based on the collected data. We wrap up by summarizing our work and touch on what we have planned for future work on this project.LITERATURE REVIEWIt is important when using a thread pool architecture to configure the thread pools to best optimize program efficiency. Pyarali et al [1], investigate ways in which to evaluate techniques for improving the RT-CORBA [2] thread pools. Pyarali et al [1] present their results of running different thread pool configurations and conclude that thread pools are an important CORBA capability mainly because they allow control of system resources. Although CORBA [2] is not directly relevant, the research done to optimize thread pool design by [1] can be applied generally to any thread pool model. Pyarali et al examine several thread pool properties and analyze their contribution towards thread pool optimization. The thread pool properties include whether or not the threads are created statically or dynamically, the thread priority, thread stack size, request buffering, and thread borrowing. All of these properties make it possible to optimize a thread pool on a given system architecture where the thread pool is a solution to a well defined problem. Several of these thread pool properties defined by [1] will be used in our own research 2CSCI 693 Research Paper: BOYCHUCK, Davidto analyze the differences in performance of our recursive threaded programming models when tested in a dynamic environment.Although thread pools seem like an obvious solution to eliminating the cost incurred during thread creation in a threaded programming model, there are still costs associated with initializing a thread pool. Obviously, if the cost of initialization is higher than the cost of individual thread creation, then the performance of a thread pool will be poor when compared to a thread-per-request [3] thread model. Ying et al. [3] in their paper “Analysis of optimal thread pool size”, seek out to improve thread pool performance by finding an optimum number of threads for a thread pool. Ying et al describe several currently used rules of thumb for initializing thread pool size and explain why these rules lead to poor performance. Ying et al then describe mathematically a way to calculate the optimum thread pool size based on a probability distribution, where the probability distribution would have to be calculated by observation of thread usage for a given amount of time. The formula described by [3] requires that you have the probability distribution as well as the timings on a particular operating system for creating a thread and switching the context of a thread.It is also important when analyzing threaded programming models that you can extract information relevant to thread performance. Cantrill et al. [4] have written a library that will extract this information and display it to the user. The program, called ThreadMon [4], displays thread state information, as well as which thread is mapped to which Light Weight Process (LWP), and (in the case of multiprocessor machines) the CPU on which each LWP is running. The ThreadMon [4] library has good coverage of thread information such as the time that threads are spent in various states. Some example thread state information accessible is time spent blocking, as well as the number of threads running at a given time. Although this library would 3CSCI 693 Research Paper: BOYCHUCK, Davidbe valuable to use for our analysis of recursive threaded programming models, it is not publicly available. Thankfully, Cantrill et al describe to some degree the methods, and important system locations, for extracting this helpful information. We will take advantage of this information while extracting useful thread metrics in our own experimentation.TECHNICAL BACKGROUNDBefore we discuss the metrics that we will be using to compare our two recursive thread program models, we will first present define what recursive thread program is. For the purposes of the experimentation done here we define a recursively threaded program to be a program that spawns threads inside of threads via recursive function calls. The two programs that we present in this