

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


A DYNAMIC RECONFIGURABLE COMPUTER WITH A DYNAMIC GENETIC ALGORITHM By KAZUNORI NISHIMURA Associate of Arts Central Christian College of Kansas McPherson, Kansas 2002 Bachelor of Science Oklahoma State University Stillwater, Oklahoma 2006 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE July, 2008 ii A DYNAMIC RECONFIGURABLE COMPUTER WITH A DYNAMIC GENETIC ALGORITHM Thesis Approved: Dr. Sohum Sohoni Thesis Advisor Dr. Louis Johnson Dr. Weihua Sheng Dr. A. Gordon Emslie Dean of the Graduate College iii ACKNOWLEDGEMENT First of all, I thank my parents, Mr. Kazuo and Ms. Reiko Nishimura, for their support. Without their help, I would not be able to come to U.S.A and continue studying for a long time. Also I thank my sister and brother for their patience and my host family for their support. I appreciate all faculty members that I took classes from. Among the faculty members, I give special remarks to my thesis committee members, Dr. Sohum Sohoni, Dr. Louis Johnson, and Dr. Weihua Sheng. Dr. Sohoni offered me the opportunities to use research resources and advice to complete my research. Without his help, I would not be able to complete my research. Also I thank to people in Writing Center for their help in the thesis edition and the lab assistants in CEAT labs and Alvin Ng for special accommodation on labs resources. Kazunori Nishimura iv TABLE OF CONTENTS Chapter Page CHAPTER 1 INTRODUCTION ............................................................................................................ 1 1.0 Definition of reconfigurable computer .............................................................................. 2 1.1 Motivation ......................................................................................................................... 4 1.2 Thesis Organization .......................................................................................................... 6 CHAPTER 2 REASONS AND PROBLEM STATEMENT .................................................................. 7 2.0 Reasons for our proposal ................................................................................................... 7 2.1 Problem Statements ......................................................................................................... 10 CHAPTER 3 RECONFIGURABLE MULTICORE SYSTEM WITH GENETIC CONTROL ......... 13 3.0 Assumptions .................................................................................................................... 13 3.0.0 Configuration constrains ........................................................................................ 13 3.0.1 Data centric approach............................................................................................. 18 3.0.2 Inforuction Buffer .................................................................................................. 19 3.0.3 Brief idea of architecture of proposed system ........................................................ 19 3.1 Optimization Technique .................................................................................................. 20 3.1.0 General Genetic Algorithm: Background information .......................................... 21 3.1.1 Specialized General Genetic Algorithm................................................................. 26 3.1.1.0 Dynamic population ............................................................................................ 26 3.1.1.1 Off by one theory ................................................................................................ 31 v TABLE OF CONTENTS Chapter Page 3.1.1.2 Multiple Crossover Operation with multiple parents .......................................... 33 3.1.1.3 Fitness function ................................................................................................... 34 3.1.1.4 Running BEST .................................................................................................... 38 CHAPTER 4 STATIC RECONFIGURABLE SYTEM: GENETIC ALGORITHM EVALUATION 40 4.0 Reason for static reconfigurable computer implementation ............................................ 40 4.1 Assumptions for Simulation ............................................................................................ 41 4.1.0 Stochastic Inforuction Generator ........................................................................... 41 4.1.1 Dependencies and inforuction stream .................................................................... 44 4.2 Genetic algorithm for the static operation ....................................................................... 45 4.3 Simulation settings and simulation results ...................................................................... 48 4.4 Simulation Results and Observations .............................................................................. 52 CHAPTER 5 DYNAMIC RECONFIGURABLE SYSTEM ................................................................ 67 5.0 Specific details of the dynamic genetic algorithm .......................................................... 67 5.1 Simulation settings .......................................................................................................... 70 5.2 Simulation Results and Observations .............................................................................. 72 CHAPTER 6 CONCLUSION AND FUTURE WORK ....................................................................... 82 6.0 Problems .......................................................................................................................... 82 6.1 Future work ..................................................................................................................... 83 6.2 Applications .................................................................................................................... 86 6.3 Conclusion ....................................................................................................................... 87 vi TABLE OF CONTENTS Chapter Page APPENDIXIES .............................................................................................................................. 89 APPENDIX A: REFERENCES ................................................................................................... 89 APPENDIX B: TABLES AND FIGURES: SETTINGS AND RESULTS ................................. 93 VITA ........................................................................................................................................... 123 vii LIST OF FIGURE Table Page FIGURE1.1: GRAPH OF YEARS VERSUS NUMBER OF TRANSISTOR ON A SINGLE CHIP [2] ................................... 1 FIGURE1.2: LIST OF THREE ESSENTIAL CHARACTERISTICS FOR THE PROPOSED SYSTEM ................................. 6 FIGURE2.1 LIST OF PROBLEM STATEMENT WE WILL SOLVE TO CREATE THE PROPOSED SYSTEM .................... 12 FIGURE3.1 OPERATION OF THE GENETIC ALGORITHM .................................................................................... 24 FIGURE3.2 OPERATION FLOWCHART FOR THE GENETIC ALGORITHM .............................................................. 24 FIGURE3.3 OPERATION FLOWCHART FOR THE MODIFIED GENETIC ALGORITHM ............................................. 33 FIGURE3.4 OPERATION FLOWCHART FOR THE FITNESS FUNCTION .................................................................. 38 FIGURE4.1 OPERATION FLOWCHART FOR THE INFORUCTION GENERATION FOR EACH CYCLE ......................... 44 FIGURE4.2 OPERATION FLOWCHART FOR THE GENETIC ALGORITHM FOR STATIC OPERATION ........................ 46 FIGURE4.3 OPERATION FLOWCHART FOR THE SIMULATION STAGE OF GENETIC ALGORITHM FOR STATIC APPLICATION ........................................................................................................................... 47 FIGURE4.4 APITCGEN FOR DIFFERENT TYPES OF SYSTEMS .......................................................................... 53 FIGURE4.5 APITCGEN FOR DIFFERENT TYPES OF SYSTEM ............................................................................ 54 FIGURE4.6 APITCALL WITH BEST FOR DIFFERENT TYPES OF SYSTEMS ....................................................... 55 FIGURE4.7 SPITCALL WITH BEST AMONG SYSTEMS ................................................................................... 55 FIGURE4.8 APITCALL WITH AVER FOR DIFFERENT TYPES OF SYSTEM ........................................................ 57 FIGURE4.9 SPITCALL WITH AVER AMONG SYSTEMS .................................................................................. 58 FIGURE4.10 APITCALL WITH BEST FOR DIFFERENT TYPES OF SYSTEM WITH MODIFIED ALGORITHM ......... 59 FIGURE4.11 SPITCALL WITH BEST AMONG SYSTEMS WITH MODIFIED ALGORITHM .................................... 59 FIGURE4.12 APITCALL WITH AVER FOR DIFFERENT TYPES OF SYSTEM WITH MODIFIED ALGORITHM ........ 60 FIGURE4.13 SPITCALL WITH AVER AMONG SYSTEMS WITH MODIFIED ALGORITHM ................................... 60 FIGURE4.14 CHANGES ON NUMBER OF CORES IN APITCGEN FOR BEST ...................................................... 61 FIGURE4.15 CHANGES ON NUMBER OF CORES IN APITCGEN2 FOR BEST .................................................... 61 viii LIST OF FIGURE Table Page FIGURE4.16 CHANGES ON NUMBER OF CORES IN APITCALL FOR BEST ...................................................... 63 FIGURE4.17 CHANGES ON APITCALL WITH DIFFERENT LENGTH OF SIMULATION FOR BEST ....................... 63 FIGURE4.18 CHANGES ON APITCALL FOR BEST WITH DIFFERENT ITERATION ............................................ 64 FIGURE4.19 CHANGES ON APITCALL FOR BEST WITH DIFFERENT STALL TRIGGER..................................... 65 FIGURE5.1 RECONFIGURATION TIME DETERMINATION PROCESS .................................................................... 68 FIGURE5.2 OPERATION FLOWCHART FOR THE DYNAMIC GENETIC ALGORITHM .............................................. 69 FIGURE5.3 BRIEF DESCRIPTION OF FLOWCHART OF THE DYNAMIC GENETIC ALGORITHM .............................. 70 FIGURE5.4 SPITCBEST WITH DYNAMIC SYSTEMS ........................................................................................ 73 FIGURE5.5 APITCBEST WITH DYNAMIC SYSTEMS ........................................................................................ 73 FIGURE5.6 SPITCGEN WITH DYNAMIC SYSTEMS .......................................................................................... 74 FIGURE5.7 APITCGEN WITH DYNAMIC SYSTEMS ......................................................................................... 74 FIGURE5.8 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE NUMBER OF CORE) ................................. 76 FIGURE5.9 NUMBER OF RECONFIGURATIONS (CHANGING THE NUMBER OF CORES) ....................................... 77 FIGURE5.10 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES) ................................... 77 FIGURE5.11 AVERAGE NUMBER OF RECONFIGURATION (CHANGING THE DELAY CYCLES FOR 6 CORES CASE) ............................................................................................................................................. 78 FIGURE5.12 APITCGEN CHANGES FROM THE CHANGE OF INFORUCTION BUFFER ........................................ 79 FIGURE5.13 APITCGEN CHANGES FROM THE CHANGE IN CYCLES OF EACH APPLICATION ........................... 80 FIGUREB.1 APITCGEN FOR BEST FOR EACH SETTING ............................................................................... 101 FIGUREB.2 APITCGEN FOR AVER FOR EACH SETTING .............................................................................. 101 FIGUREB.3 APITCGEN FOR LOG FOR EACH SETTING ................................................................................ 102 FIGUREB.4 APITCGEN FOR MAT FOR EACH SETTING ................................................................................ 102 FIGUREB.5 APITCGEN FOR FLP FOR EACH SETTING .................................................................................. 103 FIGUREB.6 APITCGEN FOR MEM FOR EACH SETTING ............................................................................... 103 FIGUREB.7 PITCGEN FOR BEST WITH AMONG 2 CORES SYSTEMS ............................................................. 104 FIGUREB.8 PITCGEN FOR BEST AMONG 4 CORES SYSTEMS ...................................................................... 104 ix LIST OF FIGURE Table Page FIGUREB.9 PITCGEN FOR BEST AMONG 6 CORES SYSTEMS ...................................................................... 105 FIGUREB.10 PITCGEN FOR BEST AMONG 8 CORES SYSTEMS .................................................................... 105 FIGUREB.11 PITCGEN FOR BEST AMONG 10 CORES SYSTEMS .................................................................. 106 FIGUREB.12 PITCGEN FOR BEST AMONG 12 CORES SYSTEMS .................................................................. 106 FIGUREB.13 PITCGEN FOR BEST AMONG 14 CORES SYSTEMS .................................................................. 107 FIGUREB.14 APITCGEN FOR BEST FOR EACH SETTING WITH MODIFIED ALGORITHM ................................ 107 FIGUREB.15 PITCGEN FOR BEST AMONG 2 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 108 FIGUREB.16 PITCGEN FOR BEST AMONG 4 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 108 FIGUREB.17 PITCGEN FOR BEST AMONG 6 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 109 FIGUREB.18 PITCGEN FOR BEST AMONG 8 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 109 FIGUREB.19 PITCGEN FOR BEST AMONG 10 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 110 FIGUREB.20 PITCGEN FOR BEST AMONG 12 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 110 FIGUREB.21 PITCGEN FOR BEST AMONG 14 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 111 FIGUREB.22 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 111 FIGUREB.23 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 112 FIGUREB.24 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 112 FIGUREB.25 APITCGEN FOR DYNAMIC SYSTEM WITH 6 CYCLE DELAY ...................................................... 117 FIGUREB.26 APITCGEN FOR DYNAMIC SYSTEM WITH 8 CYCLE DELAY ...................................................... 117 FIGUREB.27 APITCGEN FOR DYNAMIC SYSTEM WITH 10 CYCLE DELAY .................................................... 118 FIGUREB.28 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 2 CORES) 118 FIGUREB.29 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 4 CORES) 119 FIGUREB.30 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 6 CORES) 119 FIGUREB.31 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 8 CORES) 120 FIGUREB.32 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 10 CORES) ..................................................................................................................................... 120 FIGUREB.33 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 12 CORES) ..................................................................................................................................... 121 x LIST OF FIGURE Table Page FIGUREB.34 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 14 CORES) ..................................................................................................................................... 121 FIGUREB.35 AVERAGE NUMBER OF RECONFIGURATION (CHANGING THE DELAY CYCLES FOR ALL CORES CASE) ............................................................................................................................. 122 xi LIST OF TABLES Table Page TABLE 1.1 DIFFERENT TYPES OF RECONFIGURABLE COMPUTERS IN OUR DEFINITION ..................... 4 TABLE 3.1 COMPARISON OF TWO METHODS OF RECONFIGURATION ............................................. 17 TABLE4.1 PERFORMANCE OF SIMULATION STATIONS ................................................................... 49 TABLE4.2 STOCHASTIC DATA OF INFORUCTION GENERATION IN THE PERCENTAGE ..................... 50 TABLE4.3 AMOUNTS OF INFORUCTION THAT EACH ARCHITECTURES CAN PROCESS IN THE GIVEN TIME UNIT ............................................................................................................. 51 TABLE4.4 COMMON SETTING FOR EACH CONFIGURATION IN SIMULATION ................................... 51 TABLE4.5 VARIABLES AND THEIR POSSIBLE SETTINGS ................................................................. 52 TABLE4.6 STATISTICAL DATA OF SPITCALL WITH BEST ........................................................... 56 TABLE4.7 STATISTICAL DATA OF SPITCALL WITH AVER .......................................................... 58 TABLE5.1 COMMON SETTING FOR ALL SIMULATION ..................................................................... 71 TABLE5.2 VARIABLE SETTING FOR EACH SIMULATION ................................................................. 71 TABLE6.1 PREVIOUS DYNAMIC APPROACH AND MAJOR PROBLEMS ........................................... 84 TABLE B.1 CHANGES IN STOCHASTIC INFORMATION OF INFORUCTION GENERATOR – PART 1 ..... 93 TABLE B.2 CHANGES IN STOCHASTIC INFORMATION OF INFORUCTION GENERATOR – PART 2 ..... 94 TABLE B.3 SETTING OF STATIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 1 ........ 94 TABLE B.4 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS) – PART 2 ............ 95 TABLE B.5 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS)  PART 3 ............. 96 TABLE B.6 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS)  PART 4 ............. 97 TABLE B.7 SIMULATION RESULT OF S001 IN PITCGEN – PART 1 ................................................ 97 TABLE B.8 SIMULATION RESULT OF S001IN PITCGEN – PART 2 ................................................. 98 TABLE B.9 SIMULATION RESULT OF S001IN PITCGEN – PART 3 ................................................. 99 xii LIST OF TABLES Table Page TABLE B.10 SIMULATION RESULT OF S001IN PITCGEN – PART 4 ............................................. 100 TABLE B.11 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 1 113 TABLE B.12 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 2 114 TABLE B.13 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 3 115 TABLE B.14 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 4 116 1 CHAPTER 1 INTRODUCTION As a result of the major technology boost after World War II, some of the things that we had not even imagined have come true. Examples of such kinds of dreams are space stations, robots, digital cameras, mobile phones, handhelds, portable PCs, and portable music players. Many technological improvements and realization of dreams came from the invention of the transistor, and continuing improvement of transistor technology following Moore’s Law, which predicts the growth of number of transistor in a single chip. This law predicts that the total number of devices in a chip will double every 12 months in the 1970s and the number of transistors will grow slower in the 1980s (it would be double every 24 months) [1]. Figure1.1: Graph of years versus Number of Transistor on a single chip [2] 2 The dramatic increase in the number of transistor in a single chip (depicted in Figure 1.1 above), and the reduction in gains from aggressive superscalar techniques has led to multicore architecture for the CPU. Examples of multicore CPU architectures are Intel® Core 2™ Duo, Core 2™ Quad or cell processor that was invented by IBM and Toshiba [3] – [5]. Since multicores superscalar architecture can have more processing power compared to single core [3] – [5], it is natural trend to change the computer architecture to obtain higher processing performance. Also there is another trend in the area of computer architecture research. Many computer researchers set their focus on the reconfigurable computer since the reconfigurable computer has the potential to achieve higher processing performance compared to the processing performance of single core CPU architecture [6] – [8]. Even though we are using the same terminology reconfigurable computer, it has different meaning and represents different system for different researches. In other words, there is no clear single definition for the reconfigurable computer, and the meaning depends on the purpose of the research. Therefore we clarify the definition of reconfigurable computer in this study with several examples. 1.0 Definition of reconfigurable computer Among different definitions of reconfigurable computer, there is one common property that we can easily find. The reconfigurable computer has the ability to adjust functionalities or architecture to achieve the correct functionalities or the superior performance. Keeping in mind this common property, we use the term reconfigurable 3 computer as the computer system that has the abilities to adjust the architecture and functionalities to achieve a specific objective. In our definition of reconfigurable computer, we can identify several different types of reconfigurable systems. One example of a reconfigurable system is the Central Processing Unit (CPU) of a general purpose computer. The current CPUs in the market have the multiple functionalities to implement the different logical operations and arithmetic operations. Examples of logic operations are AND, OR, XOR and NOT. Examples of arithmetic operations are addition, subtraction and multiplications. Among the different operations, the control command in the instruction set reconfigure the CPU to achieve the correct functionalities to process information [9]. Another example of reconfigurable computer is the current computer system. Since we have sufficient chips on the current highend motherboards, we can operate the computer systems without any expansion cards. Although it is not necessary to install expansion cards, we usually enhance the performance of the computer system by installing graphic cards and sound cards and so on. In this case, we modify the system configuration by adding more resources to improve the performance. In the previous paragraph, the first case also shows the example of runtime or dynamic reconfigurable computer. The dynamic reconfigurable computer changes its system configuration or architecture during the time when operations of the system are executing. The second example displays the offline or static reconfigurable computer. The static reconfigurable computer changes its characteristics during the time when the system is not active or is turned off. In the other words, the reconfiguration is not only happened when the system is on. Table 1.1 summarizes the types of reconfigurable computer we describe in this section. 4 Table 1.1 Different types of Reconfigurable computer in our definition Types Purpose Performance or Correctness of the functions Method Static or Dynamic 1.1 Motivation In the area of computer architecture research, we know that specialized computer architecture has better performance than general computer where the specific application or purpose is concerned. There is no doubt for this statement since this fact is very clear from results of almost all previous researches in the area of computer architecture research. The better performance is obtained from the optimized architecture that is corresponding to the purpose of the system, such as mathematical operation, logical operation, graphical operations, encoding or decoding and so on. (In this paper from this point, the term optimized stands for “specialized” to obtain the current best performance configuration as far as we find so far.) However, the specific computer architectures also have several disadvantages in the purpose that the system is not specialized for. This characteristic of computer in general is similar to the characteristics of human brain. Most people definitely have some specific fields that they are better in, than other areas, even though these superiorities and inferiorities in performance are different for each person. Some people might be good at memorizing mathematical equations, but they might be not good at 5 playing music from music score without any practice. Other people might have superior capability in computer research and programming but they might not be good at writing papers. Examples that we described are limited to academic subjects, but we can find these performance differences all over human life from daily life to business world. These characteristics are based on the environmental causes, such as what we had more interest in, what we studied, how we grew up, and so forth. In other words, we optimized ourselves or our brain for the characteristics that we need or what we use more often. The proof of this performance optimization is clear on where we are concerned about the acquisition of languages. The children who grew up with English in their schools can speak English fluently compared to the children who did not speak English at all. This accommodation of language abilities does not only appear in speaking, but also in listening, writing, and reading. For example, children who grew up with Japanese can distinguish between the meaning of words, which can have several different meanings, even though they might sound similar or exactly same. There is one significant characteristic difference between conventional computer architecture and human brain, even though we usually use analogy of human brain to explain computer operations. Human brains optimize performance or improve performance up to certain age, but normal computer does not change architecture after the production stage. Some reconfigurable computer changes architecture to obtain better performance for the specific tasks, but this specialization does not work in all situations. Due to the technological improvements in the recent era, the complex reconfigurable computer is not just a dream any more. With continuous changing 6 motivation towards the technological front, we try to emulate the adjustability of human brain in a computer system using the reconfigurable computer. More specifically, we try to implement the flexibilities of human brain that is adjusting architecture for what we process currently. Therefore the heterogeneous reconfigurable computer that we want to propose has the three essential properties as summarized in Figure 1.2. 1.2 Thesis Organization The remainder of the thesis is consisted of 6 Chapters. We start to discuss the reasons and problems statement for our proposed system in Chapter 2. In Chapter 3, we discuss the general idea of proposed system and the background concepts for the proposed system. In Chapter 4, we will do simulation to get the proof that the genetic algorithm can be used for simulation of computer architecture at high level. Also in this chapter, we briefly go over stochastics to introduce new assumption. The simulations in this chapter are implemented with static reconfiguration of computer architecture. Chapter 5 describes simulations of the proposed system and observations from the results of simulations. In Chapter 6, we finally conclude this thesis and offer suggestions for future research. Figure1.2: List of three Essential Characteristics for the Proposed System • Automatically adjustable architecture • Dynamic or runtime Reconfiguration • Optimization for specific objectives. 7 CHAPTER 2 REASONS AND PROBLEM STATEMENT 2.0 Reasons for our proposal In this study, we propose a multicore reconfigurable CPU as emulating the processing power of human brain. In this section, we go over several observations of the general reconfigurable computer to describe reasons of our choice. Additionally, we mention about problems that need to solve to create the system with the three properties listed in Figure 1.2: automatic reconfiguration, dynamic reconfiguration, and optimization for the specific target. Assume we have a single reconfigurable core which implements the CPU, and our system has control unit which calculates the optimized architecture or configuration. Each time we try to reconfigure the system we cannot process the information during the reconfiguration time. We call this interval the reconfiguration penalties. If we try to implement the static reconfigurable CPU, the system does not try to process any information during reconfiguration. Therefore these penalties are not so important for the static implementation of the reconfigurable computer. As we describe in Chapter 1, we attempt to implement a system with the dynamic reconfiguration. The insignificance 8 of the reconfiguration penalties is not same for our system. For the dynamic single core reconfigurable system, we definitely add one more term to calculate the total time needed to execute all information. We define the time unit we use for calculation of total Cycle Time (CT) as Cycle Time, which is time necessary to execute the specific instruction or the set of instruction. Relationship between total CT for static reconfigurable CPU and total CT for dynamic reconfigurable CPU for single core case is shown in expression (2.1) – (2.4) (Expression (2.2) is calculation for static reconfigurable CPUs and expression (2.3) is calculation for dynamic reconfigurable CPUs). We remark on one important fact of CT before moving to multicore case. The CT would not be steady for both dynamic and static reconfigurable CPU. In other words, the time is dependent on the type of architecture we implement, and information we process during the period we are interested in. Also CT is measured as the average time obtained from tremendously large samples, since the instruction is not always executed in the same length of time. # 2.1 # 2.2 # _ __ # 2.3 # 2.4 where CT is Cycle Time, CTSI is Cycle Time for the Specific Instruction, dif is different, inst is instruction, TCT is Total Cycle Time, RP is reconfiguration Penalties, recon is reconfiguration, t is time, and ex is extra 9 As we see in expression (2.1)  (2.4), we have several different terms in reconfiguration penalties. Extra time to find the optimized configuration in the controller unit is usually longer than the benefit of reconfiguration. Therefore the dynamic system might have several cases that end up with worse performance in term of total CT compared to the static system, due to the reconfiguration penalties. As a result, the average total amounts of information that the system can process in the given time interval cannot produce outstanding benefit from reconfiguration. For the single core operation, the dynamic reconfiguration would not have sufficient motivation to implement, since it might not produce enough benefits in term of processing power as described above. Next we evaluate multicore reconfigurable CPU briefly. If reconfiguration of cores in systems has dependencies in terms of processing information, which means that all cores in systems cannot process information during reconfiguration, the result of simple observation would be similar to the conclusion from observation of single core case. Therefore we need to develop a new system whose reconfiguration of each core is independent of each other. In other words, the remainder of cores, which would not reconfigure, can still execute information during the process of reconfiguration. In this situation, the dynamic system equation in expression (2.1)  (2.4) cannot be used to determine total CTs. We have to determine reconfiguration penalties with more complex equations such as expression (2.5) and (2.6). The complexity of calculation increases tremendously, even though expression (2.5) and (2.6) look like simple equations. So we cannot determine benefit of reconfiguration as easy as evaluation of single core case if we use CT as performance measurement. 10 # 2.5 # # 2.6 2.1 Problem Statements From the previous argument, we need to develop new performance measurement, which we can easily use to determine the characteristics of dynamic systems and to compare the results with several different systems to find a better one. Also new measurement should be able to apply for static systems to compare performance between dynamic systems and static systems. As we discuss about performance of architecture, we not focus on the silicon area that is necessary for a whole system. We set our focus on processing power of systems. To determine processing power of systems, we cannot forget about one fact: results of performance measurements are dependent on benchmark programs we choose. For example, a result from one performance measurement shows outstanding benefits for a specific architecture, but the other performance measurement displays poor abilities for the same architecture. These differences come from the fact that different benchmark programs have different sequences of instructions, different measurement techniques, and different purposes of measurements which they are specialized for [10] – [13]. As a result of such specialization, we usually need to use several different performance measurements to determine benefits for implementing a where CT is Cycle Time, CTSI is Cycle Time for the Specific Instruction, dif is different, inst is instruction, TCT is Total Cycle Time, RP is reconfiguration Penalties, recon is reconfiguration, t is time, and ex is extra 11 specific architecture. Also most benchmark programs are developed for conventional computer system, which might not be as dynamic as we propose. Some of the bench mark programs might be developed for reconfigurable computers, but we would not measure performance of brainlike computers easily with them. This is because our proposed system has more flexibility to adjust system configurations and architectures dynamically to purpose of systems. As we describe previously, our brainlike computer is changing architectures according to the information we need to process while the machine executes the information. Therefore a result of performance measurement might not be always the same, since processing of information would change as we run the system. From this point of view, we need to develop the new measurement method that we could use for our purpose. In the previous paragraph, we emphasize the importance of developing new performance measurements for reconfigurable systems to compare each individual system configurations. We also need to develop a performance measurement for reconfigurations or performance prediction. Performance prediction has the huge impact on final overall system performance measurement. The reason of the importance of performance prediction comes from the fact that the optimization technique decides timings for automatic reconfiguration and candidates for next configuration based on the information obtained from performance prediction. Also the optimization technique is critical for our system. The relationship between control algorithm and performance of systems can be explained with analogy in a branch prediction. If branch prediction has great precision, the performance benefit from branch prediction becomes more obvious compared to systems without branch prediction. In automatic reconfigurable system, the 12 system with poorly developed optimization algorithm demonstrates only poor performance compared to the static systems. On the other hand, we can observe superior performance of dynamic automatic reconfigurable system from systems with welldeveloped optimization algorithm. Therefore control algorithm, its decision criteria, and performance prediction need to be developed carefully to obtain the sufficient results. As we close this section, we summarize the problems obtained from our observation in Figure 2.1. With these problems in mind, we go over proposed brainlike system and its assumption in the next chapter. Figure2.1 List of Problem Statement we will solve to create the proposed system • What kinds of evaluation technique or bench mark will we use? • What kind of performance prediction will the optimization algorithm use? • What kind of optimization algorithm will we implement for the system? • What kind of performance measurement will we use for the system? 13 CHAPTER 3 RECONFIGURABLE MULTICORE SYSTEM WITH GENETIC CONTROL 3.0 Assumptions Before describing the general idea of our system with optimization technique and simulation technique we implement, we introduce several assumptions we use for this study. These assumptions are used efficiently to decrease the number of small problems and to reduce the complexity of problems in simulation of our system. 3.0.0 Configuration constrains There are two methods that we can use to find architecture configuration or design in reconfigurable computers. One of the methods is that we start designing the computer configuration from scratch. We design the candidate architecture with all aspects, such as number of gates logics and functions implemented in the architecture, without any previous information and any design constrains except the maximum number 14 of gate available in a reconfigurable core. This method can find the best architecture candidate in terms of performance for a specific purpose. Even for the single static core system, the search space of architecture configuration would be tremendously large since we have infinite choices. As a result, the search time that is necessary to find the best architecture would take more than a life time if we implement any search algorithm without blueprints. This search time issue would cause more serious problems for dynamic multicore system. The search time that is necessary to find next configuration of each cores would take longer than a life time of production. The time needs for the search become too long for any numbers of cores if we do not use appropriate design constrains or predesigns. Since all system change processing information as time goes, the “best” configuration of the past moment would not produce sufficient performance benefit if the search time is too long. In the other words, there are some opportunities that performance of system after reconfiguration would be worse than the performance of system prior to reconfiguration. This is caused by the “inappropriate” change of system architectures. As we describe about reconfiguration penalties in expression (2.3)  (2.4), search time to find the next configuration for all cores should include evaluation of performance measurement. In dynamic system, each core would be redesigned to find better performance for each chance for reconfiguration. Therefore if search time is too long such as the time necessary to find the next configuration from scratch, the performance benefits from reconfiguration also diminishes. To reduce search time, we might be able to use the current designs or configurations of architecture as the start point of design. Such kinds of information might help to reduce search time that is necessary to find next configurations, but we 15 cannot guarantee that the previous configuration would be efficient starting point for the architecture designs if we adjust systems for processing information in current time. We can verify this fact with a simple example. Assume a simple system which is processing “information A” for a long time and current configuration optimized to process “information A” as “configuration M”. If “information A” changes to “information B” which require similar set of instructions to process, “configuration M” would be a sufficient starting point to improve performance. However, the opposite case would cause a different result. “Configuration M” would not be worthy of use if “information A” changes to “information C,” which requires completely different pattern of instructions compared to the instruction pattern necessary to process “information A”. In the two previous methods, we cannot have any characteristic information for each candidate we evaluate to find the optimized candidate beforehand. Therefore we should measure performance of architectures after the design is completed. To compare the candidates of next architecture configuration in the optimization algorithm, we need to wait until several other candidates are designed and measured. We can reduce the time necessary for multiple candidate designs by making the design process as simultaneous operation instead of sequential single design process. However, even with such kind of systems we cannot reduce the time necessary to complete any single candidate. Therefore these methods are not appropriate for our dynamic system. The reconfigurable computer with predefined configuration is the method we use. This method has several benefits that increase the performance of our system. The first benefit is that the performance increases from reduction of the time necessary to design core architecture. Since we only use architectures that are preconfigured, we do not 16 have to spend time for designing better architecture from the beginning. This idea is similar to the method of hierarchical design of Very Large Scale Integrated chip (VLSI) [14]. In the VLSI, we use the predesigned cells to create a larger and more complicated circuit. The cells used in the VLSI designs are extensively measured and welldesigned to be specialized for certain objectives. In our system, we use welldesigned architectures which are implemented in reconfigurable cores. As we describe at the end of the previous paragraph, we only use welldefined core architecture which we know all performance characteristics such as power consumption, processing power, and Silicon area necessary to create. This fact generates several other benefits. We can reduce reconfiguration penalties due to the performance measurements of the next configuration candidates. We would know maximum performance of each architecture configurations without any assumptions since we can evaluate performance prior to use. We can also calculate the maximum performance of a multicore system with simple arithmetic from the single core specifications. This wellestablished knowledge of performance can reduce the complexity of the optimization algorithm and the work load to find better configurations in the algorithm. In other words, the optimization algorithm is too complicated and time consuming without any prior knowledge of characteristic information since performance information is necessary to find better candidates. The reduction of reconfiguration penalties with preconfigured and welldefined systems are related to improvement in the processing performance. We go over one more benefit that is related to cost of implementation. Since we only use preconfigured architectures that we have the possibility to use, we can reduce the size of each reconfigurable core to the minimum requirement which is necessary to implement 17 the largest architecture we have. This benefit is related to the cost of Silicon area that is required to implement each core. If we are designing the architecture of a core from scratch, we cannot obtain the information for the minimum size requirement which might be used in our system. Therefore we have to prepare overhead areas up to the limit of the Silicon area we can use, and sizes of the reconfigurable core would be more than the necessary area, even though the size of the final configuration might be much smaller than what we prepare as the overheads. Table 3.1 displays comparison between two methods: designing from scratch and using the preconfigured designs. Table 3.1 Comparison of two methods of reconfiguration RP stands for reconfiguration penalties With Scratch With Preconfigured Designs Performance Without RP (Static) Better Worse Time Necessary to Create Next Candidate Longer Shorter Time Necessary to Evaluate Next Candidate Longer Shorter Complexity of Optimization Algorithm More Complicated Less Complicated Performance With RP (Dynamic) Worst Better Silicon Areas Used for each Design Cannot be determined prior to complete designs Can be determined with characteristics of designs 18 3.0.1 Data centric approach One of the performance measurements we can use is processing power of computers. This is one of the traditions we use in research of computer architecture. In general, we use throughput which described the number of instructions we can process in a given interval, the Instruction per Cycle (IPC), the Cycle per Instruction, and time necessary to complete specific instruction sets [9]. These measurements are focused on the number of instructions and the time needed to use the resources. There is other approach which uses data instead of individual instructions [15], [16]. This performance measurement uses the number of data or information processed in a given interval. Our brains always process several different sets of information in our daily lives. For example, the brain processes information from eyes to create what we feel to “see” such as colors, dimensional aspects, textures, and distances of objects. Also our brains process multiple sounds and identify the necessary information at the same moments. This identification comes from frequencies, amplitude, and distance from sources. If you think about motion of hands to grab something, human brains also process several different sets of information to move hands as we think. Therefore as we emulate flexibilities of the human brain, it is natural to use data centric approach for our system to find better candidates. If we consider more details of such information sets, we might consider them as millions of small instructions that have many dependencies. To reduce the effects of dependencies, we not break them down to individual instructions; instead we treat them as a set, which we define as inforuction from this point. Since we use inforuction for finding the next candidate architecture configuration, our data centric approach needs to define several different types of inforuction to create the performance 19 measurement details. Using these types of information, all preconfigured architectures are measured with their characteristics such as the amount of inforuction they can handle in a given time interval. In other words, we know all performance measurements in term of the processing power of inforuction. 3.0.2 Inforuction Buffer If we refer to architecture of superscalar processors in [9], we have an instruction buffer which stores instructions temporary till they feed to each individual pipeline. This mechanism allows us to control the flow of instructions and to utilize each pipeline as much as possible. We implement a similar mechanism in our system, which is identified as inforuction buffer. As we decide to use data centric approach, inforuction buffer stores each type of inforuction in different buffers. So each time inforuction is prefetched, the inforuction is separated with types of inforuction and feed into the corresponding inforuction buffer. The inforuction in the inforuction buffer is processed in the order they are fed in, which is the same order as firstin and firstout (FIFO) operation. This order reduces probabilities that we have dependencies among information. Therefore the inforuction buffer controls the flow of information and utilizes each core as much as possible. 3.0.3 Brief idea of architecture of proposed system The General concept of our system would be similar to a cell processor [5] or similar to a tree. Therefore we explain our system architecture with an analogy to a tree. For a tree, we have one big trunk which holds minerals, some nutrients, and water 20 obtained from the roots. Then the trunk sends these substances to the branches. The branches have different number of leaves that can implement photosynthesis, which uses sunlight to convert some nutrients and water and carbon dioxides into oxygen and some useful nutrients. Each leaf has also different amounts of chlorophyll which determines the capability of photosynthesis in a given day. In our system, the trunk corresponds to the inforuction buffer, the number of leaves on a branch corresponds to the number of cores in a system, and different amounts of chlorophyll corresponds to different architecture configurations we implement. Therefore our system has one big information buffer which stores and sends the inforuction to each core at the certain time and each core has input and output port at the same location in the architecture design. Therefore we can switch configurations of cores without any connection problems. 3.1 Optimization Technique In this section, we introduce the genetic algorithm as the optimization technique. The genetic algorithm is one of the newly developed field and one of the hottest topics in research of computational intelligence. Application of genetic algorithm to research of computer architecture is not new. The algorithm is used for research of VLSI design to find the optimized area and optimized number of VIAs for the situation [17] – [21]. These references and [22] give more details for genetic algorithm which we do not go over deeply. In this study, we only provide the minimum knowledge to understand operations of the genetic algorithm. 21 3.1.0 General Genetic Algorithm: Background information The genetic algorithm is inspired from mechanism in the natural world [22]. As we try to emulate flexibilities of a human brain with multicore processors, the genetic algorithm emulates the optimization mechanism of species such as natural selection, evolution, and mutation. In the natural world, we know that there is natural selection and theory of evolution, which are proposed by Charles Darwin. The natural selection theory tells us that the species with characteristics more suitable to environment will prosper, and the species which cannot survive in the environment will decline in number, and will be terminated eventually [23]. The evolution theory tells us that the species would change its characteristics based on environment through generations [23]. These two theories can explain as we go over the history of Earth. For example, the dinosaurs prospered in a certain time in the ancient earth, but they do not survive in the current era. There might be several different hypotheses for reasons of termination, such as climate changes due to strike of large meteor, and survival races with the small size Mammal species that started to prosper. All of those hypotheses tell us that there might have been dramatic environmental changes in the ancient era and the dinosaurs could not adjust their characteristics to the changes in the environment. There is another mechanism which keeps the varieties of species. In the natural selection mechanism, each species would converge to the optimized characteristics, but the other mechanism generates the diversity in the species. This mechanism is called mutation. With mutation, the genes of the offspring generation would have different traits from the parent generation. We introduce several terms which are commonly used in the genetic algorithm prior to going over the operations of the genetic algorithm. Most definitions that we use 22 come from [22]. To implement the genetic algorithm, we need to decide the targets of optimization and how we evaluate systems with the objective we define. The targets of optimization are anything that can be evaluated with numeric values from distance of travels in the Traveling Salesman problems (TSP) to areas and numbers of VIAs in VLSI designs [21] [24] [25]. The method of evaluation is called the fitness function and numerical values obtained from fitness functions are called the fitness values. The numeric data of fitness values represents quality of measurement of the objective. To establish the fitness function, we also need to decide how we represent systems with some DNA like combinations, which is called chromosome. In other words, chromosome is representation for a possible candidate configuration of a whole system. Each entry in chromosomes represents some traits of a system, as each set of entries in DNA represent some kind of characteristics. For example of TSP, chromosome is the traveling path which travelers will follow to visit necessary cities, and the entry in chromosome or gene corresponds to a specific city which he has to visit. Set of multiple chromosomes is called population. At the initial stage, general genetic algorithm produces a set of chromosomes up to population size which is defined by designer, and would not change the population size for the entire algorithm. We usually use random generation method, in which each gene in chromosomes is set randomly to include various chromosomes in population. We identify these initially generated candidates as population of the first generation. After we set population, we pick up parents of offspring with some methods such as random, weighted random, and other methods. With chosen parents, we use some methods to create set of offspring. One of the commonly used methods in process of offspring 23 generation is called crossover. With the crossover operation, children have some common pattern of genes from both parents. As the name implies, crossover generates the offspring by exchanging some gene pattern between parents which is similar to mechanism of gene pattern succession in the offspring. Example of crossover is displayed in Figure 3.1. After generating a candidate or candidates of next population, we implement the mutation operation. This changes part of gene pattern randomly. Example of mutation is also displayed in Figure 3.1. Then we evaluate generated offspring and old generation with fitness functions. With fitness values and superiorities of fitness values that we decide, we sort entire set of chromosomes which contains both offspring and the entire population of previous generation. Then we implement termination mechanism to adjust the number of chromosomes in the population to the size of population we decide to use. After creating the new population, we designate this set as population of the second generation. In other words, we increment generation number each time we create new population. The processes after production of population of the first generation are repeated continuously till certain conditions are achieved. This condition is identified as stopping criteria. Examples of stopping criteria are optimized candidate have sufficient fitness value or maximum generation we define is passed. Figure 3.2 shows a flowchart of the genetic algorithm. The term iteration is used to count the number of repetitions for the entire flowchart in Figure 3.2. 24 Figure3.2 Operation flowchart for the genetic algorithm Start Initialization Generation Evaluation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the chromosome randomly 2.) Generation Stage a. Choose the parents b. Implement Crossover c. Implement Mutation 3.) Evaluation Stage a. Evaluate with Fitness function 4.) Termination Stage a. Sort the population with result of 3‐a.) b. Choose the chromosome to terminate c. Generate new population 5.) Check Stage a. Check for stopping Criteria Figure3.1 Operation of the genetic Algorithm A C E A E B A B C B A E A.) Cross over operation with multiple offspring case A B C A E B A C E B A E A C E B A E A C A B A E B.) Mutation operation 25 There is significant benefit for applying the genetic algorithm as the optimization technique. The genetic algorithm is an optimization algorithm which has both global search and local search abilities. With the crossover operation, we implement the local search. With mutation operation, we implement the global search, which checks randomized candidate other than similar candidates which we produce with crossover. In conventional optimization algorithm, most algorithms have only one search method, not both. Also the conventional optimization technique uses the sequential evaluation, in which the algorithm generates only single candidate, evaluates and compares with the current system. Example of sequential optimization is simulated annealing [25]. For the genetic algorithm, we use the parallel optimization, which generates multiple candidates, evaluate, and compares with the previous population. We can find better candidates more efficiently since we check more candidates simultaneously and choose better candidates. In this section, we discuss the general genetic algorithm. As we close this section, we define two terms: global optimum and local optimum according to [23]. The local optimum is better candidate than all other candidates in terms of fitness values among results of the current search. The global optimum is best candidates among all other local optimum in terms of fitness values. Relationship between these optimums is similar to cost of gas in a certain state. We can find cheapest price of gases in a city when we compare prices inside a city. This cheapest price or local minimum might not be cheapest price all over the state or global minimum since we might find better result from another city. This terminology would be used in this section. In next section, we go over the genetic algorithm that we implement in our system 26 3.1.1 Specialized General Genetic Algorithm In the previous section, we introduce background information for the genetic algorithm. The actual genetic algorithm that we implement in our system has more functions and is slightly different from the general genetic algorithm. In this section, we describe the characteristics of the specialized genetic algorithm. 3.1.1.0 Dynamic population As we explained in the previous section, the basic genetic algorithm has a fixed size of population which is not changed for the entire algorithm. The choices of appropriate size of population are one of the hottest topics in research of genetic algorithms. The reason is that the size of the population is deeply related to abilities of the optimization and time necessary to complete the search algorithm. We can explain this with a simple example. Assume we have the genetic algorithm which implements a fixed number of generations. If we increase the size of the population, the possibilities to find optimized candidate or the best candidate would be greater than with smaller sizes, but calculation costs of each generation would also expand. On the other hand, if we reduce the size of the population, calculation costs will get smaller but, the possibilities to find the best candidate will also decrease. In our dynamic system case, we want to reduce the calculation cost as much as possible, but at the same time we want to increase possibilities to find better candidates as much as possible. So the determination of a good population size is too sensitive of an issue since the choice of the population changes the functionality of algorithm dramatically. To overcome issues related to finding the best population size, we use the dynamic population size approach instead of the fixed 27 population size as [26]. With this approach we start from the relatively smaller initial population size which we define. After the genetic algorithm starts, we do not know the population size since the size is automatically adjusted according to the current condition of the optimization process. There are several characteristics we have to define for the dynamic population approach. Those characteristics are what would be the trigger of change the population size, how we will change it, and how much we will change it. If we do not choose each category carefully, the dynamic population algorithm does not work correctly or simply works as the fixed size population approach. The first question we tackle is what would start the process of changing the size of the population. Since the dynamic population is part of the genetic algorithm which uses the fitness values to determine whether candidates are better or not, we can use the fitness values of the population to trigger changes of the population size. There are several different statistical data of the fitness values. Examples are the best fitness value, the worst fitness value, the mean fitness value, and the median fitness value of the population. Within these values, we use the average or mean fitness value of the current population and the mean fitness value of the group which consisted of both the current population and the candidates which we generated. This idea came from a question that was asked by then Ph.D. Student WenFung Leong during one of my course presentations. Since the average fitness value displays the performance of the optimization process as a whole in a given moment, the dynamic population would ensure proper resource management for the search ability of the genetic algorithm. Each 28 time we obtain the new fitness values of candidates and the new fitness values of the current population, we initiate the process of the dynamic population algorithm. As we decide when we will change the size of the population, we need to decide how we will change it according to the difference between two average fitness values. There are two different resource management strategies we can use to determine how we will change the population size. These two methods of resource management are similar to methods that students commonly use in their studying for final exams. Some students prefer spending more time for subjects that they are very good at, and spending less time for topics they hate. As a result, students would answer the question extremely well for the subject they studied and cannot answer the questions they did not study well. Or more simply, students become specialized in specific subjects they like. On the other hand, other types of students would spend more time on subjects which they are not good at and spend less time for the subjects which they feel strong in. These people use time where it is necessary to spend it. Comparing these two types of students, the second type of student has more chances to have better grade point average (GPA). This example is true among different disciplines. Back to method of resource management, we describe and evaluate two types of strategies for increasing the chance of generating better average fitness values. The first type of resource management technique uses more computational resources when we have better average fitness values and uses less when we have poor results. In other words, we spend more time where we find better average fitness values and less time for where we cannot find good average fitness values. This strategy might find a local optimum quicker than the other method, but one problem of this method is that the local 29 minimum we find is not always the global minimum as we describe at the end of the previous section. For the second strategy, we utilize more resources when we have a hard time to find the better average fitness values and less when we can easily find better fitness values. This method spends more time where we cannot find better average fitness values and less time where we find better average fitness values. The comparison of these two strategies in a real situation can be explained with an analogy of openbook/open note exam. Assume we try to solve two different types of questions: questions that we have enough knowledge to solve and questions that we do not have any idea how to solve. To solve the first type of questions, we only need to check the correctness of our memory with books to obtain better scores. In this case, we just have to use resources which relate to the concepts we need. If we just go over each topic in the text books, it is just wasting time and we will end up running out of time to solve the other questions. To solve the second type of questions, we cannot review specific topics since we do not have any idea how we can solve them. We have to go over each topic briefly to find any related concepts which can be used to solve the questions. If we randomly choose specific chapters in books to read in detail, the exam time is too short to find necessary information. The first method of taking exams demonstrates a similar situation as the case when we know the fitness value of the global optimum. This is not the situation where we are during the search, since we do not know what the global optimum is. Therefore, we have to apply the second strategy instead of the first method. In other words, we will increase population size when we have a hard time to find better average fitness values or very close to optimum (either global or local) and reduce the size when improvement in average fitness values is sufficient. In this 30 method, we would have better opportunities to find the global optimum. There is one problem while applying the second strategy: the population size might get too small to keep operation of the algorithm correct if we constantly improve the average fitness values. We discuss the solution for this issue in the latter section of this chapter. We have already decided the timing of change and the method of change, but we have not yet finished the argument for the degree of change in the population size. This question has also several different strategies such as the constant fixed change method, dynamic fixed change method and proportional change method. We briefly go over each strategy with problems and benefits. The first strategy is simple enough to implement, since the size of change in the population is defined at the beginning of the algorithm. Therefore, we do not have to change it and also we do not have to calculate the degree of change according to the improvement in the average fitness value. The problem of this approach is very obvious, the size always changes constantly no matter what the current size of the population we have, and how much we improve the average fitness values. In extreme example, a result of twentyfive percent improve in the average fitness value cause the same degree of change in the population size as a result of one percent decrease in the average fitness value. Also the impact of change does not take into consideration the change in the population size. If we only use a fixed number of candidates to change the population size, the impact of change would not be efficient when the size of population is large. For example, we would double the size of the population if we change its size from 10 to 20. However, there will be only ten percent of increase in the size of population if we change the size from 100 to 110. The impact of the changes in the average fitness value in the previous two examples is not the same. The second 31 approach requires several conditional statements to implement the algorithm, so the calculation cost will increase slightly compared to the first approach. The degree of changes in the fitness values are reflected in the second approach, but the impact of changes that is dependent on the population size is not included in this algorithm. The third approach treats both the degree of changes and the impact of changes. Instead of a fixed size algorithm implemented in the previous two approaches, it uses the proportional changes which are dependent on both the population size and the degree of changes in the average fitness values. The calculation cost for implementing the third method is slightly greater than the second approach. Even with the disadvantage in the calculation cost, the third approach is worth implementing, since we can change the population more dynamically compared to the other approaches. 3.1.1.1 Off by one theory We now explain the method we implement to avoid errors in the algorithm due to the reduction of the population size. Since we implement crossover operation, we definitely require at least more than two chromosomes in the population. The method is that we insert new sets of the chromosomes into the current population whenever the population size does not meet the minimum size requirement of the algorithm. New sets of the chromosomes are generated with some randomization mechanism. Before we explain randomization mechanism to fix violation of the minimum size requirement, we go back to several observations we discuss previously. In section 3.0.1, we describe that the current adapted core architecture configuration in the dynamic system would not guarantee good performance in the future. This statement is true when we observe processing performance of computer systems. For short time observation, we 32 can say that current configuration would produce sufficient performance to use as seeds of randomized chromosomes, since the contents of inforuction buffer changes slowly unless it is completely empty. Therefore the current configuration would offer several hints to find the next configuration. If we only add the same configuration to the population, the abilities of both global and local search would decrease. Therefore we need to generate randomized candidates from the current configuration. In the randomization process, we generate candidates according to the off by one theory. This theory tells us that it would be better to change the architecture of only one reconfigurable core in the randomization process. This theory is derived from the careful observation of the assumption we made earlier. We assume that during the process of reconfiguration the reconfiguring core cannot process any inforuction. Therefore, if we increase the number of core which reconfigure, it implies the number of cores that cannot process inforuction in several intervals. As a result, performance of the system would decrease significantly during reconfiguration. Hence, candidates that only change one core would yield similar performance as the current configuration of the system. In most cases, generated candidates would have less performance in the processing power due to the reconfiguration penalties. From this observation, we create candidates which randomize only single core from the current configuration, and we insert generated chromosomes into the population to prevent failure of the algorithm and to maintain diversity in the population. Figure 3.3 illustrates the flow of the modified genetic algorithm. 33 3.1.1.2 Multiple Crossover Operation with multiple parents There are several papers which study about the effect of multiple crossover operations in the genetic algorithm. Examples of such studies are [27] [28] [29]. The multiple crossover operators have one important benefit. This method enhances the global search abilities of the genetic algorithm. Even though the crossover operation implements local search, each different crossover operator would search through different search spaces. The variety of children in each generation would increase compared to the implementation of single crossover operation. Also, the multiple parents would increase the global search ability, since we choose several different sets of parents Figure3.3 Operation flowchart for the modified genetic algorithm Start Initialization Adjustment Evaluation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the chromosome randomly 2.) Adjustment Stage a. Change the population size 3.) Generation Stages a. Choose the parents b. Implement Crossover c. Implement Mutation 4.) Evaluation Stage a. Evaluate with Fitness function 5.) Determination Stage a. Evaluate the next population size 6.) Termination Stage a. Sort the population with result of 4a.) b. Choose the chromosome to terminate c. Generate new population 7.) Check Stage a. Check for stopping Criteria 8.) Stop Stage a. The best candidate is picked up as the output of algorithm Generation Determination Minimum size? Not Satisfied Satisfied 34 for each type of crossover operator. So many traits of chromosomes are effectively used to create the next population. 3.1.1.3 Fitness function In this section, we talk about the most important topic of the genetic algorithm. This is not an exaggerated expression since the result of fitness function is used for control of reconfiguration and control of the dynamic population. We go over several facts that are used to develop our fitness function. To compare each configuration of the system, we can use the processing performances of configurations after we complete the process of reconfiguration since they are simple enough to calculate. Even though we know the processing characteristics of each core which we obtain from measurements, the actual performance of cores and systems might be lower than what we calculate. There are three types of barriers that make system performance lower. One of the barriers is the stall. The stall is the time we cannot have the full abilities of processing power since some infoructions are not ready to process [9] or we have too much stock of inforuction in the inforuction buffer. This is caused by dependencies in inforuction. In the stall condition, systems cannot obtain any new infoructions. Another barrier has a similar effect as the stall, but the cause of this barrier is slightly different. We name this barrier emptyrunning. As the name implies, the system does not store sufficient amounts of specific types of infoructions in the information buffer compared to the maximum performance we have. We explain the problem of this situation with an example. We feed each type of infoructions into the corresponding inforuction buffer each time we prefetch. Each reconfigurable core in the system processes infoructions from this set of inforuction buffers. If we have sufficient pre 35 fetched infoructions for all types of inforuction buffers, the system can process as much as possible with its maximum potential and there is no problem for this situation. However, if the inforuction buffer contains fewer amounts of some types of inforuction, cores cannot utilize the fullprocessing power as we calculate. It can only process the amounts of inforuction in the inforuction buffer. After it completes processing, it becomes idle or runs with the emptied inforuction buffer till the next set of infoructions is ready. Another barrier is reconfiguration penalties. During reconfiguration, the processing power of systems decreases compared to full specification since several cores are isolated or excluded from our system. After reconfiguration, the isolated cores become active to process infoructions. Therefore these performance changes during the process of reconfiguration also make the processing power difficult to use as the fitness values of our system. With all three of these barriers together, we cannot use processing power directly to determine the fitness values of a given system configuration. The appropriate fitness function should treat all three barriers. We use the predicted amounts of infoructions we can process in a certain time interval as our fitness values. The detail of fitness function is described in expression (3.1). The time parameter t is used in expression (3.1). This time parameter should be longer than the reconfiguration penalties since we know the performance of a dynamic system during reconfiguration is lower than the system which stays the same as the current configuration. If we take a longer time interval for the parameter t, calculation costs of reconfiguration would increase dramatically since the fitness function emulates behaviors of systems to predict amounts of information we might process. To predict the 36 performance of dynamic systems, we have to predict the amount of infoructions which will be generated in the time interval t since the inforuction we need to process in the future time is unknown. # # # # 3.1 The approach we take for prediction of the future infoructions uses the similar concept in the neural network system [30]. In the neural system, we train the network with some sample patterns which model the operation of the system. The neural network trains to obtain the correct result or desirable results in terms of purpose of the system with the differences of simulated results, and preferable results. For our system, we will train our prediction mechanism with the data of the generated infoructions which are fed into our inforuction buffer whenever we do not reconfigure the system. Our training method is straightforward. We take the data for occurrence of each inforuction for a specific time interval. This time interval is related to the time parameter (t) we use in the fitness function. As a result of the fitness value evaluation, we conclude that we do not have to reconfigure our system, since the current system configuration might have better performance within the time interval (t). Therefore we might not have to reconfigure our system during the time interval. At the same time, we do not have to evaluate the candidates with the genetic algorithm. We use the time interval in which the 37 optimization process does not operate, and resources which is usually used in the optimization algorithm. We discuss the meaning of the data of inforuction occurrences in the later chapter. We will evaluate the impact of misprediction. The misprediction occurres when the data for occurrence does not correspond to the actual behavior of systems. It happens when sets of inforuction produced are changed dramatically from what we observe. The impact caused by the misprediction would not be severe since it is softened by the inforuction buffers. This is because the sets of inforuction in the inforuction buffer should be processed prior to the sets of inforuction predicted with the prediction mechanism. In other words, we always have some portion of infoructions that we will definitely process since they are the stored infoructions in the inforuction buffer. Therefore, the ratio of amounts of mispredicted inforuction handled in the fitness function to the infoructions that are predicted to be handled would be always less than 1. Even though there is a possibility of misprediction, our prediction mechanism represents the actual behavior of systems more accurately than the simplest prediction method, which assumes to have exactly the same number of each inforuction during our prediction. As we close this section, we show the flowchart of the fitness function in the Figure 3.4. Our fitness function is a short time simulation of the system since we need to determine the performance in the future for both types of systems: the system with the current configuration and the system with the candidate configurations during the process of optimization for the multicore system. 38 3.1.1.4 Running BEST The genetic algorithm will converge to the optimum when we use algorithms with a large number of generations. Hence, the algorithm needs long time to obtain the optimum. Even if we use large number of generations, the optimum obtained is either local or global. There is no guarantee we can get global optimum without prior knowledge. As we implement the genetic algorithm as part of dynamic system, the large generation for convergence would be problematic, since the larger generation needs more time to compute the fitness values. Therefore we cannot wait the algorithm to converge, and we should set the generation we want to use as the stopping criteria. Instead, we use Figure3.4 Operation flowchart for the fitness function Start Initialization Generation Processing Evaluation Time t passes? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Memorize the current inforuction buffer and current pattern of inforuction generation 2.) Generation Stage a. Generate the inforuction pattern the same as 1‐a.) 3.) Processing Stage a. Increment the internal clock b. Process the # of inforuction for the current processing power 4.) Check Stage a. Time check i. Check whether the time interval t is passed? b. Stall check i. Check whether the stall is happened or not 5.) Evaluation Stage a. Evaluate the fitness function Stall? Not happened happened 39 the running best or optimized candidate as our next candidate, which is the candidate with best fitness values that we evaluate through our algorithm. In other words, we stop the genetic algorithm with a specific generation, and obtain the best candidate from the given population. Since the chosen candidate is the best candidate in the population, we can use this approach for the best candidate that we can find within the limited resources. 40 CHAPTER 4 STATIC RECONFIGURABLE SYTEM: GENETIC ALGORITHM EVALUATION 4.0 Reason for static reconfigurable computer implementation Even though we have several examples which apply the genetic algorithm to research of computer architecture [17] – [21], we do not have an example of the genetic algorithm applied as the optimization algorithm to find better configuration candidates in terms of processing power of CPUs. We can prove the performance of the genetic algorithm to find the optimized candidates through the implementation of a static reconfigurable computer, which is similar to a cell processor. Also we can develop the framework of simulation that we can use for the dynamic system. In addition to these benefits, the results of simulation can be used as the performance of specialized static computer, which can be used to compare with our proposed system. Therefore we should implement a static reconfigurable computer. 41 4.1 Assumptions for Simulation We describe the important assumptions that are necessary for the simulation for the dynamic system in Chapter 3. We will discuss assumptions that we will use for the static reconfigurable systems and will introduce the new mechanism with a new assumption that would be used in both simulations of static and dynamic systems. Assume we have the multicore system described in section 3.0.3. Each of architecture configurations of cores we use in our system is well designed. The characteristics of each architecture configuration are well measured in terms of amounts of possible inforuction each core can process during a certain time unit. This measurement is called Inforuction Per Clock Cycle (IPCC). Since we implement superscalar architecture in each core, IPCC for each core has amounts of each types of inforuction that a single core can process simultaneously during a given time unit. Before discussing the details of genetic algorithm in the next section, we will introduce the new concept: stochastic inforuction generator. 4.1.0 Stochastic Inforuction Generator Before introducing the stochastic inforuction generator, we will go over the basic idea of stochastics. Most definitions come from [31] – [33]. When we observe result of a fairsixfaced dice roll, we get faces from 1 to 6. For short time observations or from small number of samples of a single dice roll, occurrence of each faces dynamically change as we roll, and we cannot find steady result in frequencies of occurrence for each face. When we observe fairly large numbers of dice roll or we have sufficient numbers of samples of dice roll, there would be steady data for occurrence of each face, which is 42 one sixth for each face in this case. In other words, if we observe some system for a long time, we would find stochastic data or probability information in behaviors of the observed system. In the previous example, the stochastic information we get is frequencies of occurrence of each face. Since this is the representation of system behavior, we can predict the behavior of the given system with probabilities. The example of prediction is probability of faircoin toss. We know probabilities of occurrence for each side of the coin would be one half. Therefore, if we toss a coin significant number of times, we can predict that we will have about half of toss as heads and the other half as tails. In real situations, there are dependencies among occurrence of each instance. Since the dependencies change the probabilities of occurrence, our prediction of occurrence is more difficult. However, if we find out all dependencies, the predictions would correspond to the actual system behavior. If we observe a single computer system with a certain simulation for a long time, or if we observe multiple computes with same settings, there should be stochastic information for occurrence of each type of instructions. We prove this statement with contradiction. Assume we do not have any stochastic information or probabilities for occurrence of each instruction. In other words, the instructions we process is decided randomly. For such situation, we cannot reproduce a result of simulation, even if we use the exactly same setting. However, the normal simulations implemented in some benchmark programs definitely have steady results that we can reproduce with the same settings. With reproducible results, we justify our accomplishments. Simulators or benchmark programs are designed to reproduce the data if we use the exactly same setting since they produce the same sets of instructions for the same settings. On other 43 hand, if we have different sets of instruction, the result of simulation would not be reproducible. This is contradictory to what we assume: we cannot reproduce the same result since the instruction is randomly generated. Therefore there exists the stochastic information for patterns of instruction generation in a simulator, which is dependent on the type of application. This assumption is based on the observation of a specific purpose application. For example, the mathematical application software would produce more instruction related to mathematical operation compared to other software. If we are watching a movie on the computer, the instruction related to graphics and sounds would be more than the normal operation of the system. For our system, we would have stochastic patterns in inforuction generation that are different for each types of application. With stochastic information for occurrence of each types of inforuction, we can generate infoructions to simulate real behavior of systems. We call this stochastic method of generating inforuction as stochastic inforuction generators. We will remark one more fact for the stochastic inforuction generator. The stochastic information should obtain from data that is consisted of large numbers of samples since validity of the stochastic information increases with larger amounts of data due to the reduction of the effect from the noise or unexpected data. Also we need to use stochastic inforuction generator for longer cycle to increase accuracy and precision of the simulation. The actual process of inforuction stream generation is illustrated in Figure 4.1. As Figure 4.1 displays, we use a random number generator to generate the actual inforuction in each cycle. We cannot match the stochastic information used to the generate infoructions with the stochastic information from actual generated infoructions in each cycle. We can only observe the random generation of infoructions in a short time. 44 However, if we observe the inforuction generation pattern for a long time, we can get similar stochastic information as information used to generate inforuction stream. From this point, this method can be used for a short cycle operation, which does not have any clear stochastic information for a generation pattern. Figure4.1 Operation flowchart for the inforuction generation for each cycle 4.1.1 Dependencies and inforuction stream Up to this point we do not have any mechanism to implement for dependencies of infoructions. For our simulation, instead of implementing the actual dependency mechanism, we randomly insert an extra cycle in which no new data is fed into the inforuction buffer. This corresponds to NO OP instruction in regular computer terminology. To model system accurately, the numbers of dependencies correspond to the Start Load stochastic Set Ref Check the type Stop 1.) Load Stage a. Load stochastic data of inforuction generation 2.) Set Ref Stage a. Use random generator to set the reference point 3.) Check Type Stage a. Check what type of inforuction will be generated (Find the value k which satisfies the following expression: Σ Pith type ) 4.) Generation Stage a. Generate the inforuction according to check stage result 5.) Check # of Generated Stage a. Check the number of inforuction generated for this cycle is the same as the number we defined or not Completed Not Generation Generate all? 45 numbers of total inforuction we will process in our simulation. To compare the systems with the same number of cycles fairly, we use the exact same inforuction stream. This means we have the same stochastic data, the same number of inforuction, the same numbers of dependencies, and the same sequence for each inforuction. 4.2 Genetic algorithm for the static operation The genetic algorithm we implement for the static system has the same characteristic as dynamic algorithm expect the several differences that come from system properties. For the static application, we do not change system configuration while the system processes infoructions. Therefore we do not have to worry about reconfiguration penalties and reduction of performance due to reconfiguration. The objective of the static reconfigurable computer is to find the optimized configuration for the system which has the “best” performance for given application or application sequence. So fitness values of the static reconfigurable computer are the total time unit necessary to complete all inforuction. As we describe previously, we have to worry about the reduction of processing performance due to stall and emptyrunning, since stall and emptyrunning will increase the necessary time unit to complete all inforuction. The flowchart of the static genetic computer is described in Figure 4.2. We go over several stages which is different from the dynamic operation we described at the previous chapter. 46 Most significant difference between dynamic operation and static operation is location of the genetic algorithm or the stage of simulation. For dynamic systems, we are running simulation while we use the genetic algorithm to find better candidates of the next configuration. For this application, we run the miniature of simulation in the process of fitness function evaluation. For the static operation, we use the genetic algorithm after we simulate a system to find the fitness values. The details of simulation flow are shown in Figure 4.3. Figure4.2 Operation flowchart for the genetic algorithm for static operation Start Initialization Adjustment Simulation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the configuration of cores randomly 2.) Adjustment Stage a. Insert randomly generated candidates to satisfy the minimum population size 3.) Generation Stages a. Choose the parents b. Implement Crossover c. Implement Mutation 4.) Simulation Stage a. Simulate the time necessary to complete the inforuction sets 5.) Determination Stage a. Evaluate the next population size 6.) Termination Stage a. Sort the population with result of 4‐a.) b. Choose the chromosome to terminate c. Generate new population 7.) Check Stage a. Check for stopping Criteria 8.) Stop Stage a. The best candidate is picked up as the output of algorithm Generation Determination Minimum size? Not Satisfied Satisfied 47 This figure is similar to Figure 3.4 which displays the flow of fitness function in dynamic systems. The differences between these two flowcharts are at the last conditional or check statement. For the fitness function of dynamic system, the amount of infoructions processed is variable, and the cycle in which we simulate remains constant. The simulation for static systems is targeted to obtain the difference in time cycle for given amounts of infoructions we need to process. From these reason the stall condition is implemented in the different location in the two flowcharts. Another difference between the two flowcharts is the method we use to generate chromosomes to adjust the population size. Remember for the dynamic system, we introduce the offbyone theory, which tries to change configuration of only one core in Figure4.3 Operation flowchart for the simulation stage of genetic algorithm for static application Start Generation Processing Stall? Not Happened Happened Stop 1.) Generation Stage a. Generate the inforuction pattern which is pre‐configured for the purpose for the system 2.) Processing Stage a. Increment the internal clock b. Process the # of inforuction for the current processing power 3.) Stall Check Stage a. Check whether the stall is happened or not 4.) Information check a. Check whether all inforuction is completed or not Complete? Completed Not completed 48 the process of generating the extra candidate for adjusting population size. This theory is to avoid the severe reconfiguration penalty from reconfiguring multiple cores at once. As we described previously, we do not have to worry about the reconfiguration penalty in the static system. Therefore we insert chromosomes which are randomly generated to ensure the varieties in the population. Since there are local optimum issues for the optimization process, the randomly chosen configuration would give more chances to find global optimum. One more remark for simulation method we can use for both dynamic and static system as we close this section, which is how we implement the stall. As we describe, the stall is time necessary to “catch up” with the current inforuction flow to avoid the hardware hazard. Therefore the stalls are detected when any types of inforuction buffers have greater amounts of infoructions than the dimension we predefined. During the stall, the internal clock is incremented without generating new inforuction sets. The stall will be continued until amounts of infoructions in all types of the inforuction buffers are smaller than the limitation we defined. In the next section, we will go over the simulation setting and results of the simulation with observations. 4.3 Simulation settings and simulation results In the previous section, we go over details of the genetic algorithm for the static reconfigurable CPUs. Before we show the results of simulations, we go over the details of the simulation setting. 49 We simulate our programs with 77 high end computers simultaneously to reduce the simulation time. Performance of each individual computer which runs simulation is given in Table 4.1. In our simulation, we have two types of settings. One of them is common for all static computer simulations and the other is unique for each individual simulation. We go over the details of common characteristics and then describe details of unique settings. Table4.1 Performance of Simulation Stations Performance Cumulated # of computer 77 CPU Intel® Core™2 Duo Processor 6700 @ 2.66 GHz Memory 2 GB We choose the following setting as common configuration for all static computers: number of different types of inforuction, characterization of each type of infoructions, amounts of infoructions generated in a time cycle, number of predefined architectures we use, characterization of each core architectures, number of generations in the genetic algorithm, and number of initial population. Also we set the number of maximum population we will use in the genetic algorithm as constant to improve the simulation time. We identify 4 different types of infoructions that we use to characterize the performance of core architecture and stochastic data in inforuction generation pattern for a certain application. The types of infoructions are similar to types of functional units in the superscalar processor [9]. The types of inforuction are logic, mathematic, floating point, and memory. We use 4 different pseudo applications that have unique stochastic information pattern for each inforuction. Each of application is identified as General, 50 Logic/Math, Floating Point, and Memory, which corresponds to the intensity of the infoructions for a given application. Characteristics of each application in terms of stochastic data of inforuction generation are summarized in Table 4.2. We define the characteristics of 5 different specialized cores. We name each type of architecture such as GENeral, LOGic, MATh, FLoating Point, and MEMory, which corresponds to their specialization. The performances of each type of architecture in terms of IPCC are listed in Table 4.3. The total amounts of inforuction each processor can handle are set to 8 which is the realistic number since it corresponds to the number of functional units in the superscalar processor [9]. To emulate changes of application in the systems, we randomly choose three applications from the repeated sample which consisted of the four applications we defined. The list of all inforuction generation patterns is displayed in Table B.1 and Table B.2. The common characteristic of systems we simulate is set as Table 4.4. Each inforuction stream is unique for the same length of cycle for each application we want to simulate. Table4.2 Stochastic data of Inforuction generation in the percentage where L is Logic inforuction, MA is Mathematic infoructions, FLP is Floating point infoructions, and ME is Memory infoructions. L MA FLP ME General 35 30 20 15 Logic/Math 70 18 7 5 Floating Point 5 12 80 3 Memory 15 15 10 60 51 Table4.3 Amounts of inforuction that each architectures can process in the given time unit where L is Logic inforuction, MA is Mathematic infoructions, FLP is Floating point infoructions, and ME is Memory infoructions. L MA FLP ME General 3 3 1 1 Logic 4 2 1 1 Math 2 4 1 1 Floating 1 1 5 1 Memory 1 1 1 5 Table4.4 Common setting for each configuration in simulation Setting # of total simulation 64 ( = 4^3) Total # of Inforuction prefetched 64 Size of Initial population 15 # of generation 200 Maximum size of population 450 (= 15*30) Dependencies factor .05 The rest of the settings, such as the number of reconfigurable cores we have in a system, the number of minimum cycles for each application, the number of iteration we implement, and the amounts of inforuction that trigger stall, are chosen to be variables to observe the properties of the static reconfigurable CPUs. Each individual setting for these variables is shown in Table 4.5 and the complete set of actual setting for each system we will simulate is in Table B.3 through Table B.6. 52 Table4.5 Variables and their possible settings Candidates of setting we will setting # of cores in the system 2, 4, 6, 8, 10, 12, 14 Length of each application 50, 100, 200, 400, 600 # of iterations we implement 10, 15 Stall trigger 30, 50 4.4 Simulation Results and Observations Our simulation time to complete individual configuration over 64 different application sequences are less than 5 minutes with the computer we used. Before discussing about any further observation of results, we discuss how we will compare the results of simulations among the different settings. We use a PITCGEN (Percentage of the performance Improvement in terms of Time necessary to process all infoructions Compared with the performance of GENeral core only systems) to describe the performance of our systems. Remember, our raw simulation result is time necessary to complete the inforuction streams. To obtain the performance improvement compared with the general core only system, we use the expression (4.1). We identify these ratios as a Specific PITCGEN (SPITCGEN) since these measurements are dependent on the types of application sequences in the simulation. To find the Average PITCGEN over all application sequences (APITCGEN), we use the expression (4.2). The result of the 53 calculation of APITCGEN is shown in Table 4.6. We should not forget that SPITCGEN and APITCGEN are both dependent on the setting of the systems. 1 4.1 Σ 4.2 Figure 4.4 and Figure 4.5 (Enlarged figure is in Appendix: Figure B.1 through Figure B.6) displays the APITCGEN for BEST (BEST performance we find in the whole algorithm), AVER (AVERage performance of the best performance we find in each iteration), LOG (LOGic specialized core only systems), MAT (MATh specialized core only systems), FLP (FLoating Point operation specialized core only systems), and MEM (MEMory operation specialized core only systems). Figure4.4 APITCGEN for different types of systems Left graph: result of BEST and Right graph: result of AVER. The horizontal axis displays different settings: S001 through S077 which is depicted in Table B3 through Table B6. 54 Figure4.5 APITCGEN for different types of system Top Left graph: result of LOG, Top Right: result of MAT, Bottom Left: result of FLP, and Bottom Right: result of for MEM. The horizontal axis displays different settings: S001 through S077, which are depicted in Table B3 through Table B6. Figure 4.4 and Figure 4.5 demonstrate that we seem to have about 30 % improvement in overall performance compared to GEN. This performance increase comes from the result of the static reconfiguration according to the individual inforuction streams. Since we have a different configuration for each inforuction stream, we can compare our result with the best configuration for single design core only systems. To compare the performance of our system with the best performance for single design core only systems, we use expressions (4.3) and (4.4). Since GEN systems do not produce the best PITC for all settings, this comparison provides more information about the optimization capability of our system. 1 4.3 55 Σ 4.4 Figure4.6 APITCALL with BEST for different types of systems Figure4.7 SPITCALL with BEST among systems Each entry in the graph corresponds to a specific setting (S001 – S077) in Table B.3 through B.6. 56 Figure 4.6 and Figure 4.7 demonstrate the performance of our system that is calculated from expressions (4.3) and (4.4). As we focused on Figure 4.6, the average performance improvements we achieve with our systems compared to the best performance of the single design core only systems is about 14 % and we have only positive average improvement for all settings. The 14 % increase might not seem outstanding. We look for details about this 14 % increase. Figure 4.7 demonstrate the interesting results and problems of our static systems. The problem is also one of the problems of the genetic algorithm. Each individual PICTALL is ranged from about 120 % to 40 %. Most parts of settings in Figure 4.7 demonstrate the positive performance improvement or the same performance as the best performance for single design core only systems. As we describe, the magnitude of negative performance improvement or performance reduction is momentous because it reduces our average of APICTALL, even though the number of simulations which end up with negative result is about 20 % of the entire simulation results. Table 4.6 demonstrates the several data of our simulation. Table4.6 Statistical data of SPITCALL with BEST # of simulation % of Occurrence Average Total Number 4928 100 % 14.25 % Positive PITCALL 3919 79.53 % 22.33 % Zero PITCALL 69 1.40 % 0 % Negative PITCALL 940 19.07 % 18.39 % In the theory and our simulation setting, we should not get any result with a negative SPITC since all single core only configurations, which are GEN, LOG, MAT, FLP, and MEM, are one of the subsets in our search space. Therefore, if our optimization 57 method uses the exhaustive search, we could identify these configurations as a superior configuration whenever it is appropriate. The reason why we cannot find these configurations can be explained with the one of the weaknesses of a genetic algorithm. The genetic algorithm uses a stochastic search method. During the generation of the set of candidate chromosomes, we have a certain probability to generate each candidate based on a choice of parents. There are certain probabilities that we do not check a certain candidate. Therefore, there is always nonzero probability that we cannot find the truly optimized candidate. What we end up with in our optimization process is local optimums that are different from the global optimum. This result is well displayed when we refer to Figure 4.8 which shows the APITCALL with AVER and Figure 4.9 which shows SPITCALL with AVER. AVER, which is the average of the “best” values we find over the individual iteration, is much less than the BEST, which is the “best” we find over all iterations (Data for SPITCALL with AVER is displayed in Table 4.7). The reason is that there are some probabilities that the algorithm could not find the true “optimum” within the single iteration. Figure4.8 APITCALL with AVER for different types of system 58 Figure4.9 SPITCALL with AVER among systems Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. X Axis is for the sequence pattern of applications from P01 to P64 in Table B.1 and Table B.2; Table4.7 Statistical data of SPITCALL with AVER # of simulation % of Occurrence Average Total Number 4928 100 % 16.44 % Positive PITCALL 2220 45.05 % 11.90 % Zero PITCALL 1 0.02 % 0 % Negative PITCALL 2707 19.07 % 20.68 % We can easily improve our algorithm by introducing 5 single design core only systems into the first generation of our search. With this method, we are sure the search space of simulation includes the single design core only cases. Also this modification improves the search area of the algorithm since the single design core only systems are not similar to each other. As a result, our search algorithm can produce better results. Simulation results of the modified algorithm are displayed in Figure 4.10 through Figure 4.12. The APITCGEN and SPITCGEN with BEST are in Figure B.14 through Figure 59 B.21. Compared with Figure 4.10 through Figure 4.13, our algorithm shows improvement in the optimization abilities. We have only positive performance improvements in both SPITCALL with BEST and SPITCALL with AVER. The negative SPICTALL is replaced with the zero or the positive SPICTALL since we increase the variety of systems in the first generation and we are forced to evaluate the 5 different types of single core only systems. Figure4.10 APITCALL with BEST for different types of system with modified algorithm Figure4.11 SPITCALL with BEST among systems with modified algorithm Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. 60 Figure4.12 APITCALL with AVER for different types of system with modified algorithm Figure4.13 SPITCALL with AVER among systems with modified algorithm Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. 61 Figure4.14 Changes on number of cores in APITCGEN for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. Figure4.15 Changes on number of cores in APITCGEN2 for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. 62 Figure 4.14 displays the APITCGEN for BEST. According to this figure, performance improvement compared to GEN which has the same number of cores as the comparison target, becomes the largest when we have 4 core systems, then our percentage of improvement keeps decreasing. Since the maximum amounts of total inforuction generated in a cycle are fixed, the utilization of the system compared to systems with general core only cannot be optimized if we have too many cores. The fixed amounts of inforuction generated per cycle, which is 64, come from the maximum processing power of an 8 core system. If we adjust the data to compare with the APITCGEN with 2 cores (GEN2), we observe a graph as Figure 4.15. The graph demonstrates the remarkable improvement when we increase the number of cores from 2 to 4. With this change, the maximum processing power of the system becomes half of the total amounts of infoructions generated per cycle. The result of this comparison clearly displays the diminishing performance improvement when we increase the number of cores in a system, especially if the system can only prefetch the fixed amounts of inforuction per cycle. When we increase the number of cores from 2 to 4, we efficiently reduce the cause of stalls and do not increase the probability of emptyrunning at the same time. After the 4 core system, chances of empty running are increased more than decrease in the chances of stalls. Therefore the performance is not improved as in the case of 4 cores. If we plot the same graph compared to the best single cores instead of GEN, the figure looks slightly different from the figures we observe. Figure 4.16 has similar characteristic as the previous figures up to 10 core system. However, we have the improvement for 12 and 14 cores systems. The reason why we cannot observe this 63 improvement in the previous two figures can be explained with Figure 4.11. For the comparison with the best of single design core only settings, we have more range of changes in the performance measurement for each individual setting and each individual inforuction pattern. Therefore, we observe the improvements for 12 and 14 cores. Figure4.16 Changes on number of cores in APITCALL for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. Figure4.17 Changes on APITCALL with different length of simulation for BEST Legend explains the rest settings of simulation with the following format: Number of cores: Stall trigger levels: Number of iterations. 64 Figure 4.17 displays the changes of APITCALL by changing the number of minimum length of each application. In Appendix B, we have larger size of these figures in Figure B.22 through Figure B.24. As we observe in the figures, our static system does not demonstrate any firm changes such as a monotonous decrease or increase when we change the cycles of each application. Instead of a monotonous increase or decrease, we observe the APITCALL stays in about .5 % of deviations. This comes from the differences for each length of simulation in the actual percentage of inforuction stream we simulate. Hence, we conclude this relationship as the following statement: the number of cycles for each application does not change the APITCALL significantly. Therefore our static operation seems to have steady performance improvement compared to the best configuration from single design core only system for any number of cycles. Figure4.18 Changes on APITCALL for BEST with different iteration Legend explains the rest settings of simulation with the following format: Number of cores: Cycles of each application: Stall trigger levels. 65 When we study the graph in Figure 4.18, we can still verify the local optimum issues of the genetic algorithm, since the 10 iteration data has slightly smaller APITCALL compared to 15 iteration data. Therefore we should keep the number of iterations to a relatively large number to obtain the global optimum or better performance. Figure4.19 Changes on APITCALL for BEST with different stall trigger Legend explains the rest settings of simulation with the following format: Number of cores: Cycles of each application: Number of iterations. With Figure 4.19, we cannot observe the relationship between APITCALL and the changes of amounts of inforuction that causes the stall, which corresponds to size of the inforuction buffer that is related to the hardware hazards. Some of results display the performance improvement when we have tighter stall trigger condition and the others display a decrease in the performance with the tighter constraint. The conclusion of this observation is that the change in condition of stall trigger definitely changes the APITCALL, but we cannot predict the effect in APITCALL due to the changes in the inforuction buffers from the current observations. The reason we cannot observe the 66 steady changes in the performance might comes from the following points: the inforuction buffers still have large enough size to avoid most stalls, the best configuration for single design core only systems already avoid the stalls as much as possible, the significant changes are averaged in the process of calculation of APITCALL, and/or the changes of best performance of single core only systems eliminate the proof of performance changes as in the observation of Figure 4.16. In this chapter, we introduce the static genetic reconfigurable system which demonstrates the ability to find the optimized configuration. Even though our algorithm still remains the several rooms of improvement, we obtained the positive APITC with general cores only system for all settings. With the modified algorithm, we demonstrate the better performance in the optimization to each individual application sequence. This result stands for the following statement: the genetic algorithm and our static system can change configurations of the system to obtain better performance in PITCs. We also have to emphasize the following fact: the optimization process needs prior information of the stochastic data of inforuction generation or application sequences. Without any information, our static system and the static genetic algorithm would not produce the superior results and end up with meaningless results for reconfiguration. 67 CHAPTER 5 DYNAMIC RECONFIGURABLE SYSTEM 5.0 Specific details of the dynamic genetic algorithm Since we discuss details of dynamic system in the previous sections, we will not repeat the same topic. Instead, we describe a topic which has not been discussed yet. That is how we determine the time to finish the previous reconfiguration process and start the new reconfiguration process. We have to use fixed time to estimate the fitness values, but we do not have to use the fixed time to terminate. We identify this time as reconfiguration time, which is the time we terminate the old reconfiguration process and then start the new process. If we do not choose this time interval carefully, our performance does not correspond to what we achieve in the real situation. For example, if we choose time interval shorter than the actual time for the reconfiguration of a FPGA (Field Programmable Gate Array) device, our simulation result is not realistic. Also, we have to take into consideration the calculation time for our reconfiguration process, since the timing of reconfiguration will change the performance we can get from our system. In addition to the fitness function we define in the former section, we add one more parameter that memorizes the changes of processing performance within a time 68 interval. After we find the best candidate by a genetic algorithm, we evaluate the predicted processing power of both the current configuration and the best candidate configuration. We compare these candidate performances for each time unit, beginning with the time frame we use for the genetic algorithm to the time of reconfiguration penalties. The time step we find through this process is set as the reconfiguration time that we previously defined. The flowchart of this process is shown in Figure 5.1, and the entire flowchart of the dynamic genetic algorithm is shown in Figure 5.2 and Figure 5.3. Figure5.1 Reconfiguration time determination process Start Set to the fixed time Decrement timer Check performance Satisfied Not Satisfied Stop NOT satisfied Check performance Satisfied 69 Figure5.2 Operation flowchart for the dynamic genetic algorithm Start Initialization Processing Stall? Not Happened Happened Stop Complete? Completed Not completed Flag? Genetic Algorithm Generation Better? Time? Off No Modification Yes Passed Not Passed On 70 5.1 Simulation settings In the previous chapter, we verify that the optimization ability of the genetic algorithm with the static reconfigurable system on the average. We use several fixed settings as common factors between the previous chapter and the present chapter, such as: stochastic information of inforuction generation in each application, number of different application, total number of inforuction generated in a given cycle, the number of core in a system, types of core architecture, types of inforuction, performance of each type of core architectures that are listed in Table 4.2, .Table 4.3 and Table 4.4. We change the number of generation to smaller number since we want to run this algorithm faster and the generation is the only stopping criteria as we describe. We also do not limit the size of the population inside the algorithm, but we limit the size of the population which carries over to the next implementation of the genetic algorithm. These fixed settings, Figure5.3 Brief Description of flowchart of the dynamic genetic algorithm 1.) Initialization Stage a. Set the number of application and number of iteration for each application 2.) Generation Stage a. Create the specific total amounts of information 3.) Reconfiguration Flag Check Stage a. Check whether reconfiguration is currently in the process or not 4.) Genetic algorithm Stage a. Implement genetic algorithm to find the better configuration 5.) Verification Stage a. Check whether the new configuration produce the better or not 6.) Process Stage a. Increment the time unit b. Process the # of information for the current processing power 7.) Stall Check a. Check whether the stall is happened or not 8.) Information check a. Check whether all information is completed or not 9.) Reconfiguration time Check a. Check whether the reconfiguration time is passed after the trigger of reconfiguration 10.) Modification Stage a. Change the performance of the system by adding the restriction or removing it 71 which are different from Table 4.4, are listed in Table 5.1. Also we use several variable settings as common to the setting listed in Table 4.5. The settings for variable parameter are listed in Table 5.2. All combinations of setting are listed in Table B.11 – Table B.14. As we describe in the previous chapter, we will observe the differences in the performance of static reconfigurable system and dynamic reconfigurable system. We could repeat the algorithm as we did in the static system, but we put more focus on the speed of the algorithm, since this is a timecritical operation which the environment changes as time goes and performance improvement is also dependent on the time we complete the algorithm. The fixed time we describe during the previous section is determined from the expression (5.1) Table5.1 Common setting for all simulation Setting # of total simulation 64 ( = 4^3) [same as Table 4.4] Total # of Inforuction at a time unit 64 [same as Table 4.4] Size of Initial population 15 [same as Table 4.4] # of generation 45 Maximum carry over factor (size) 4 (60 = 4*15) Dependencies factor .05 Prediction factor 2 Table5.2 Variable Setting for each simulation Candidates of setting we will setting # of cores in the system 2, 4, 6, 8, 10, 12, 14 [same as Table 4.4] Length of each application 50,100, 200, 400 Reconfiguration penalties 6,8,10 Stall trigger 30, 50 [same as Table 4.4] 72 5.1 where RP is reconfiguration penalties The choice of reconfiguration penalty is based on [34], where they said that the time necessary to complete the full programmable device is typically done in several microseconds and is dependent on the type of devices used for the reconfiguration. Also the time is dependent on the area that needs to be reconfigured [34]. In addition to the actual reconfiguration time, which is the time necessary to change the architecture, we need to think about the time to calculate the best dynamic architecture corresponding to the inforuction streams as we describe previously. The process of calculation can be implemented along with processing of inforuction in our main system. So we choose the reconfiguration penalties, which are sum of time necessary to change the architecture and time needs to calculate the optimized candidates, as 6, 8, and 10 cycles. We run the MATLAB codes with computers which have the same specifications as listed in Table 4.1. The cumulated numbers of computers used for dynamic system simulation is 102 since we simulate each individual setting with a different computer. 5.2 Simulation Results and Observations As we describe in the previous chapter and this chapter, we can use several results of observations from the previous chapter, since we use common settings. We set the model of the conventional system as general cores only and use the performance measurement of our system which is similar to what we derive in expression (4.1) and (4.2). We use the both SPITCGEN and APITCGEN, and also we use the SPITCBEST 73 and APITCBEST, in which BEST is the result of static systems in the previous chapter. The expressions to calculate SPITCBEST and APITCBEST are in expression (5.2) and (5.3). With these methods, we can easily compare the results of performance improvements from the different types of systems. 1 5.2 Σ 5.3 where BEST performance we obtain in Chapter 4 Figure5.4 SPITCBEST with dynamic systems Each entry in the graph is a specific setting (D001 – S077) in Table B.11 through B.14. Figure5.5 APITCBEST with dynamic systems 74 Figure5.6 SPITCGEN with dynamic systems Each entry in the graph is a specific setting (D001 – S102) in Table B.11 through B.14. Figure5.7 APITCGEN with dynamic systems Figure 5.4 and Figure 5.5 display the simulation results with SPITCBEST and APITCGEN. From these figures, we have to conclude that dynamic systems might not perform as well as the static systems, w
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Dynamic Reconfigurable Computer With A Dynamic Genetic Algorithm 
Date  20080701 
Author  Nishimura, Kazunori 
Department  Electrical Engineering 
Document Type  
Full Text Type  Open Access 
Note  Thesis 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  A DYNAMIC RECONFIGURABLE COMPUTER WITH A DYNAMIC GENETIC ALGORITHM By KAZUNORI NISHIMURA Associate of Arts Central Christian College of Kansas McPherson, Kansas 2002 Bachelor of Science Oklahoma State University Stillwater, Oklahoma 2006 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE July, 2008 ii A DYNAMIC RECONFIGURABLE COMPUTER WITH A DYNAMIC GENETIC ALGORITHM Thesis Approved: Dr. Sohum Sohoni Thesis Advisor Dr. Louis Johnson Dr. Weihua Sheng Dr. A. Gordon Emslie Dean of the Graduate College iii ACKNOWLEDGEMENT First of all, I thank my parents, Mr. Kazuo and Ms. Reiko Nishimura, for their support. Without their help, I would not be able to come to U.S.A and continue studying for a long time. Also I thank my sister and brother for their patience and my host family for their support. I appreciate all faculty members that I took classes from. Among the faculty members, I give special remarks to my thesis committee members, Dr. Sohum Sohoni, Dr. Louis Johnson, and Dr. Weihua Sheng. Dr. Sohoni offered me the opportunities to use research resources and advice to complete my research. Without his help, I would not be able to complete my research. Also I thank to people in Writing Center for their help in the thesis edition and the lab assistants in CEAT labs and Alvin Ng for special accommodation on labs resources. Kazunori Nishimura iv TABLE OF CONTENTS Chapter Page CHAPTER 1 INTRODUCTION ............................................................................................................ 1 1.0 Definition of reconfigurable computer .............................................................................. 2 1.1 Motivation ......................................................................................................................... 4 1.2 Thesis Organization .......................................................................................................... 6 CHAPTER 2 REASONS AND PROBLEM STATEMENT .................................................................. 7 2.0 Reasons for our proposal ................................................................................................... 7 2.1 Problem Statements ......................................................................................................... 10 CHAPTER 3 RECONFIGURABLE MULTICORE SYSTEM WITH GENETIC CONTROL ......... 13 3.0 Assumptions .................................................................................................................... 13 3.0.0 Configuration constrains ........................................................................................ 13 3.0.1 Data centric approach............................................................................................. 18 3.0.2 Inforuction Buffer .................................................................................................. 19 3.0.3 Brief idea of architecture of proposed system ........................................................ 19 3.1 Optimization Technique .................................................................................................. 20 3.1.0 General Genetic Algorithm: Background information .......................................... 21 3.1.1 Specialized General Genetic Algorithm................................................................. 26 3.1.1.0 Dynamic population ............................................................................................ 26 3.1.1.1 Off by one theory ................................................................................................ 31 v TABLE OF CONTENTS Chapter Page 3.1.1.2 Multiple Crossover Operation with multiple parents .......................................... 33 3.1.1.3 Fitness function ................................................................................................... 34 3.1.1.4 Running BEST .................................................................................................... 38 CHAPTER 4 STATIC RECONFIGURABLE SYTEM: GENETIC ALGORITHM EVALUATION 40 4.0 Reason for static reconfigurable computer implementation ............................................ 40 4.1 Assumptions for Simulation ............................................................................................ 41 4.1.0 Stochastic Inforuction Generator ........................................................................... 41 4.1.1 Dependencies and inforuction stream .................................................................... 44 4.2 Genetic algorithm for the static operation ....................................................................... 45 4.3 Simulation settings and simulation results ...................................................................... 48 4.4 Simulation Results and Observations .............................................................................. 52 CHAPTER 5 DYNAMIC RECONFIGURABLE SYSTEM ................................................................ 67 5.0 Specific details of the dynamic genetic algorithm .......................................................... 67 5.1 Simulation settings .......................................................................................................... 70 5.2 Simulation Results and Observations .............................................................................. 72 CHAPTER 6 CONCLUSION AND FUTURE WORK ....................................................................... 82 6.0 Problems .......................................................................................................................... 82 6.1 Future work ..................................................................................................................... 83 6.2 Applications .................................................................................................................... 86 6.3 Conclusion ....................................................................................................................... 87 vi TABLE OF CONTENTS Chapter Page APPENDIXIES .............................................................................................................................. 89 APPENDIX A: REFERENCES ................................................................................................... 89 APPENDIX B: TABLES AND FIGURES: SETTINGS AND RESULTS ................................. 93 VITA ........................................................................................................................................... 123 vii LIST OF FIGURE Table Page FIGURE1.1: GRAPH OF YEARS VERSUS NUMBER OF TRANSISTOR ON A SINGLE CHIP [2] ................................... 1 FIGURE1.2: LIST OF THREE ESSENTIAL CHARACTERISTICS FOR THE PROPOSED SYSTEM ................................. 6 FIGURE2.1 LIST OF PROBLEM STATEMENT WE WILL SOLVE TO CREATE THE PROPOSED SYSTEM .................... 12 FIGURE3.1 OPERATION OF THE GENETIC ALGORITHM .................................................................................... 24 FIGURE3.2 OPERATION FLOWCHART FOR THE GENETIC ALGORITHM .............................................................. 24 FIGURE3.3 OPERATION FLOWCHART FOR THE MODIFIED GENETIC ALGORITHM ............................................. 33 FIGURE3.4 OPERATION FLOWCHART FOR THE FITNESS FUNCTION .................................................................. 38 FIGURE4.1 OPERATION FLOWCHART FOR THE INFORUCTION GENERATION FOR EACH CYCLE ......................... 44 FIGURE4.2 OPERATION FLOWCHART FOR THE GENETIC ALGORITHM FOR STATIC OPERATION ........................ 46 FIGURE4.3 OPERATION FLOWCHART FOR THE SIMULATION STAGE OF GENETIC ALGORITHM FOR STATIC APPLICATION ........................................................................................................................... 47 FIGURE4.4 APITCGEN FOR DIFFERENT TYPES OF SYSTEMS .......................................................................... 53 FIGURE4.5 APITCGEN FOR DIFFERENT TYPES OF SYSTEM ............................................................................ 54 FIGURE4.6 APITCALL WITH BEST FOR DIFFERENT TYPES OF SYSTEMS ....................................................... 55 FIGURE4.7 SPITCALL WITH BEST AMONG SYSTEMS ................................................................................... 55 FIGURE4.8 APITCALL WITH AVER FOR DIFFERENT TYPES OF SYSTEM ........................................................ 57 FIGURE4.9 SPITCALL WITH AVER AMONG SYSTEMS .................................................................................. 58 FIGURE4.10 APITCALL WITH BEST FOR DIFFERENT TYPES OF SYSTEM WITH MODIFIED ALGORITHM ......... 59 FIGURE4.11 SPITCALL WITH BEST AMONG SYSTEMS WITH MODIFIED ALGORITHM .................................... 59 FIGURE4.12 APITCALL WITH AVER FOR DIFFERENT TYPES OF SYSTEM WITH MODIFIED ALGORITHM ........ 60 FIGURE4.13 SPITCALL WITH AVER AMONG SYSTEMS WITH MODIFIED ALGORITHM ................................... 60 FIGURE4.14 CHANGES ON NUMBER OF CORES IN APITCGEN FOR BEST ...................................................... 61 FIGURE4.15 CHANGES ON NUMBER OF CORES IN APITCGEN2 FOR BEST .................................................... 61 viii LIST OF FIGURE Table Page FIGURE4.16 CHANGES ON NUMBER OF CORES IN APITCALL FOR BEST ...................................................... 63 FIGURE4.17 CHANGES ON APITCALL WITH DIFFERENT LENGTH OF SIMULATION FOR BEST ....................... 63 FIGURE4.18 CHANGES ON APITCALL FOR BEST WITH DIFFERENT ITERATION ............................................ 64 FIGURE4.19 CHANGES ON APITCALL FOR BEST WITH DIFFERENT STALL TRIGGER..................................... 65 FIGURE5.1 RECONFIGURATION TIME DETERMINATION PROCESS .................................................................... 68 FIGURE5.2 OPERATION FLOWCHART FOR THE DYNAMIC GENETIC ALGORITHM .............................................. 69 FIGURE5.3 BRIEF DESCRIPTION OF FLOWCHART OF THE DYNAMIC GENETIC ALGORITHM .............................. 70 FIGURE5.4 SPITCBEST WITH DYNAMIC SYSTEMS ........................................................................................ 73 FIGURE5.5 APITCBEST WITH DYNAMIC SYSTEMS ........................................................................................ 73 FIGURE5.6 SPITCGEN WITH DYNAMIC SYSTEMS .......................................................................................... 74 FIGURE5.7 APITCGEN WITH DYNAMIC SYSTEMS ......................................................................................... 74 FIGURE5.8 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE NUMBER OF CORE) ................................. 76 FIGURE5.9 NUMBER OF RECONFIGURATIONS (CHANGING THE NUMBER OF CORES) ....................................... 77 FIGURE5.10 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES) ................................... 77 FIGURE5.11 AVERAGE NUMBER OF RECONFIGURATION (CHANGING THE DELAY CYCLES FOR 6 CORES CASE) ............................................................................................................................................. 78 FIGURE5.12 APITCGEN CHANGES FROM THE CHANGE OF INFORUCTION BUFFER ........................................ 79 FIGURE5.13 APITCGEN CHANGES FROM THE CHANGE IN CYCLES OF EACH APPLICATION ........................... 80 FIGUREB.1 APITCGEN FOR BEST FOR EACH SETTING ............................................................................... 101 FIGUREB.2 APITCGEN FOR AVER FOR EACH SETTING .............................................................................. 101 FIGUREB.3 APITCGEN FOR LOG FOR EACH SETTING ................................................................................ 102 FIGUREB.4 APITCGEN FOR MAT FOR EACH SETTING ................................................................................ 102 FIGUREB.5 APITCGEN FOR FLP FOR EACH SETTING .................................................................................. 103 FIGUREB.6 APITCGEN FOR MEM FOR EACH SETTING ............................................................................... 103 FIGUREB.7 PITCGEN FOR BEST WITH AMONG 2 CORES SYSTEMS ............................................................. 104 FIGUREB.8 PITCGEN FOR BEST AMONG 4 CORES SYSTEMS ...................................................................... 104 ix LIST OF FIGURE Table Page FIGUREB.9 PITCGEN FOR BEST AMONG 6 CORES SYSTEMS ...................................................................... 105 FIGUREB.10 PITCGEN FOR BEST AMONG 8 CORES SYSTEMS .................................................................... 105 FIGUREB.11 PITCGEN FOR BEST AMONG 10 CORES SYSTEMS .................................................................. 106 FIGUREB.12 PITCGEN FOR BEST AMONG 12 CORES SYSTEMS .................................................................. 106 FIGUREB.13 PITCGEN FOR BEST AMONG 14 CORES SYSTEMS .................................................................. 107 FIGUREB.14 APITCGEN FOR BEST FOR EACH SETTING WITH MODIFIED ALGORITHM ................................ 107 FIGUREB.15 PITCGEN FOR BEST AMONG 2 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 108 FIGUREB.16 PITCGEN FOR BEST AMONG 4 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 108 FIGUREB.17 PITCGEN FOR BEST AMONG 6 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 109 FIGUREB.18 PITCGEN FOR BEST AMONG 8 CORES SYSTEMS WITH MODIFIED ALGORITHM ....................... 109 FIGUREB.19 PITCGEN FOR BEST AMONG 10 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 110 FIGUREB.20 PITCGEN FOR BEST AMONG 12 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 110 FIGUREB.21 PITCGEN FOR BEST AMONG 14 CORES SYSTEMS WITH MODIFIED ALGORITHM ..................... 111 FIGUREB.22 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 111 FIGUREB.23 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 112 FIGUREB.24 APITCGEN FOR BEST WITH DIFFERENT SIMULATION CYCLE ................................................. 112 FIGUREB.25 APITCGEN FOR DYNAMIC SYSTEM WITH 6 CYCLE DELAY ...................................................... 117 FIGUREB.26 APITCGEN FOR DYNAMIC SYSTEM WITH 8 CYCLE DELAY ...................................................... 117 FIGUREB.27 APITCGEN FOR DYNAMIC SYSTEM WITH 10 CYCLE DELAY .................................................... 118 FIGUREB.28 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 2 CORES) 118 FIGUREB.29 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 4 CORES) 119 FIGUREB.30 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 6 CORES) 119 FIGUREB.31 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 8 CORES) 120 FIGUREB.32 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 10 CORES) ..................................................................................................................................... 120 FIGUREB.33 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 12 CORES) ..................................................................................................................................... 121 x LIST OF FIGURE Table Page FIGUREB.34 APITCGEN WITH DYNAMIC SYSTEMS (CHANGING THE DELAY CYCLES FIXED FOR 14 CORES) ..................................................................................................................................... 121 FIGUREB.35 AVERAGE NUMBER OF RECONFIGURATION (CHANGING THE DELAY CYCLES FOR ALL CORES CASE) ............................................................................................................................. 122 xi LIST OF TABLES Table Page TABLE 1.1 DIFFERENT TYPES OF RECONFIGURABLE COMPUTERS IN OUR DEFINITION ..................... 4 TABLE 3.1 COMPARISON OF TWO METHODS OF RECONFIGURATION ............................................. 17 TABLE4.1 PERFORMANCE OF SIMULATION STATIONS ................................................................... 49 TABLE4.2 STOCHASTIC DATA OF INFORUCTION GENERATION IN THE PERCENTAGE ..................... 50 TABLE4.3 AMOUNTS OF INFORUCTION THAT EACH ARCHITECTURES CAN PROCESS IN THE GIVEN TIME UNIT ............................................................................................................. 51 TABLE4.4 COMMON SETTING FOR EACH CONFIGURATION IN SIMULATION ................................... 51 TABLE4.5 VARIABLES AND THEIR POSSIBLE SETTINGS ................................................................. 52 TABLE4.6 STATISTICAL DATA OF SPITCALL WITH BEST ........................................................... 56 TABLE4.7 STATISTICAL DATA OF SPITCALL WITH AVER .......................................................... 58 TABLE5.1 COMMON SETTING FOR ALL SIMULATION ..................................................................... 71 TABLE5.2 VARIABLE SETTING FOR EACH SIMULATION ................................................................. 71 TABLE6.1 PREVIOUS DYNAMIC APPROACH AND MAJOR PROBLEMS ........................................... 84 TABLE B.1 CHANGES IN STOCHASTIC INFORMATION OF INFORUCTION GENERATOR – PART 1 ..... 93 TABLE B.2 CHANGES IN STOCHASTIC INFORMATION OF INFORUCTION GENERATOR – PART 2 ..... 94 TABLE B.3 SETTING OF STATIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 1 ........ 94 TABLE B.4 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS) – PART 2 ............ 95 TABLE B.5 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS)  PART 3 ............. 96 TABLE B.6 SETTING OF STATIC CORES (ONLY DISPLAYS VARIABLE SETTINGS)  PART 4 ............. 97 TABLE B.7 SIMULATION RESULT OF S001 IN PITCGEN – PART 1 ................................................ 97 TABLE B.8 SIMULATION RESULT OF S001IN PITCGEN – PART 2 ................................................. 98 TABLE B.9 SIMULATION RESULT OF S001IN PITCGEN – PART 3 ................................................. 99 xii LIST OF TABLES Table Page TABLE B.10 SIMULATION RESULT OF S001IN PITCGEN – PART 4 ............................................. 100 TABLE B.11 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 1 113 TABLE B.12 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 2 114 TABLE B.13 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 3 115 TABLE B.14 SETTING OF DYNAMIC SYSTEMS (ONLY DISPLAYS VARIABLE SETTINGS) – PART 4 116 1 CHAPTER 1 INTRODUCTION As a result of the major technology boost after World War II, some of the things that we had not even imagined have come true. Examples of such kinds of dreams are space stations, robots, digital cameras, mobile phones, handhelds, portable PCs, and portable music players. Many technological improvements and realization of dreams came from the invention of the transistor, and continuing improvement of transistor technology following Moore’s Law, which predicts the growth of number of transistor in a single chip. This law predicts that the total number of devices in a chip will double every 12 months in the 1970s and the number of transistors will grow slower in the 1980s (it would be double every 24 months) [1]. Figure1.1: Graph of years versus Number of Transistor on a single chip [2] 2 The dramatic increase in the number of transistor in a single chip (depicted in Figure 1.1 above), and the reduction in gains from aggressive superscalar techniques has led to multicore architecture for the CPU. Examples of multicore CPU architectures are Intel® Core 2™ Duo, Core 2™ Quad or cell processor that was invented by IBM and Toshiba [3] – [5]. Since multicores superscalar architecture can have more processing power compared to single core [3] – [5], it is natural trend to change the computer architecture to obtain higher processing performance. Also there is another trend in the area of computer architecture research. Many computer researchers set their focus on the reconfigurable computer since the reconfigurable computer has the potential to achieve higher processing performance compared to the processing performance of single core CPU architecture [6] – [8]. Even though we are using the same terminology reconfigurable computer, it has different meaning and represents different system for different researches. In other words, there is no clear single definition for the reconfigurable computer, and the meaning depends on the purpose of the research. Therefore we clarify the definition of reconfigurable computer in this study with several examples. 1.0 Definition of reconfigurable computer Among different definitions of reconfigurable computer, there is one common property that we can easily find. The reconfigurable computer has the ability to adjust functionalities or architecture to achieve the correct functionalities or the superior performance. Keeping in mind this common property, we use the term reconfigurable 3 computer as the computer system that has the abilities to adjust the architecture and functionalities to achieve a specific objective. In our definition of reconfigurable computer, we can identify several different types of reconfigurable systems. One example of a reconfigurable system is the Central Processing Unit (CPU) of a general purpose computer. The current CPUs in the market have the multiple functionalities to implement the different logical operations and arithmetic operations. Examples of logic operations are AND, OR, XOR and NOT. Examples of arithmetic operations are addition, subtraction and multiplications. Among the different operations, the control command in the instruction set reconfigure the CPU to achieve the correct functionalities to process information [9]. Another example of reconfigurable computer is the current computer system. Since we have sufficient chips on the current highend motherboards, we can operate the computer systems without any expansion cards. Although it is not necessary to install expansion cards, we usually enhance the performance of the computer system by installing graphic cards and sound cards and so on. In this case, we modify the system configuration by adding more resources to improve the performance. In the previous paragraph, the first case also shows the example of runtime or dynamic reconfigurable computer. The dynamic reconfigurable computer changes its system configuration or architecture during the time when operations of the system are executing. The second example displays the offline or static reconfigurable computer. The static reconfigurable computer changes its characteristics during the time when the system is not active or is turned off. In the other words, the reconfiguration is not only happened when the system is on. Table 1.1 summarizes the types of reconfigurable computer we describe in this section. 4 Table 1.1 Different types of Reconfigurable computer in our definition Types Purpose Performance or Correctness of the functions Method Static or Dynamic 1.1 Motivation In the area of computer architecture research, we know that specialized computer architecture has better performance than general computer where the specific application or purpose is concerned. There is no doubt for this statement since this fact is very clear from results of almost all previous researches in the area of computer architecture research. The better performance is obtained from the optimized architecture that is corresponding to the purpose of the system, such as mathematical operation, logical operation, graphical operations, encoding or decoding and so on. (In this paper from this point, the term optimized stands for “specialized” to obtain the current best performance configuration as far as we find so far.) However, the specific computer architectures also have several disadvantages in the purpose that the system is not specialized for. This characteristic of computer in general is similar to the characteristics of human brain. Most people definitely have some specific fields that they are better in, than other areas, even though these superiorities and inferiorities in performance are different for each person. Some people might be good at memorizing mathematical equations, but they might be not good at 5 playing music from music score without any practice. Other people might have superior capability in computer research and programming but they might not be good at writing papers. Examples that we described are limited to academic subjects, but we can find these performance differences all over human life from daily life to business world. These characteristics are based on the environmental causes, such as what we had more interest in, what we studied, how we grew up, and so forth. In other words, we optimized ourselves or our brain for the characteristics that we need or what we use more often. The proof of this performance optimization is clear on where we are concerned about the acquisition of languages. The children who grew up with English in their schools can speak English fluently compared to the children who did not speak English at all. This accommodation of language abilities does not only appear in speaking, but also in listening, writing, and reading. For example, children who grew up with Japanese can distinguish between the meaning of words, which can have several different meanings, even though they might sound similar or exactly same. There is one significant characteristic difference between conventional computer architecture and human brain, even though we usually use analogy of human brain to explain computer operations. Human brains optimize performance or improve performance up to certain age, but normal computer does not change architecture after the production stage. Some reconfigurable computer changes architecture to obtain better performance for the specific tasks, but this specialization does not work in all situations. Due to the technological improvements in the recent era, the complex reconfigurable computer is not just a dream any more. With continuous changing 6 motivation towards the technological front, we try to emulate the adjustability of human brain in a computer system using the reconfigurable computer. More specifically, we try to implement the flexibilities of human brain that is adjusting architecture for what we process currently. Therefore the heterogeneous reconfigurable computer that we want to propose has the three essential properties as summarized in Figure 1.2. 1.2 Thesis Organization The remainder of the thesis is consisted of 6 Chapters. We start to discuss the reasons and problems statement for our proposed system in Chapter 2. In Chapter 3, we discuss the general idea of proposed system and the background concepts for the proposed system. In Chapter 4, we will do simulation to get the proof that the genetic algorithm can be used for simulation of computer architecture at high level. Also in this chapter, we briefly go over stochastics to introduce new assumption. The simulations in this chapter are implemented with static reconfiguration of computer architecture. Chapter 5 describes simulations of the proposed system and observations from the results of simulations. In Chapter 6, we finally conclude this thesis and offer suggestions for future research. Figure1.2: List of three Essential Characteristics for the Proposed System • Automatically adjustable architecture • Dynamic or runtime Reconfiguration • Optimization for specific objectives. 7 CHAPTER 2 REASONS AND PROBLEM STATEMENT 2.0 Reasons for our proposal In this study, we propose a multicore reconfigurable CPU as emulating the processing power of human brain. In this section, we go over several observations of the general reconfigurable computer to describe reasons of our choice. Additionally, we mention about problems that need to solve to create the system with the three properties listed in Figure 1.2: automatic reconfiguration, dynamic reconfiguration, and optimization for the specific target. Assume we have a single reconfigurable core which implements the CPU, and our system has control unit which calculates the optimized architecture or configuration. Each time we try to reconfigure the system we cannot process the information during the reconfiguration time. We call this interval the reconfiguration penalties. If we try to implement the static reconfigurable CPU, the system does not try to process any information during reconfiguration. Therefore these penalties are not so important for the static implementation of the reconfigurable computer. As we describe in Chapter 1, we attempt to implement a system with the dynamic reconfiguration. The insignificance 8 of the reconfiguration penalties is not same for our system. For the dynamic single core reconfigurable system, we definitely add one more term to calculate the total time needed to execute all information. We define the time unit we use for calculation of total Cycle Time (CT) as Cycle Time, which is time necessary to execute the specific instruction or the set of instruction. Relationship between total CT for static reconfigurable CPU and total CT for dynamic reconfigurable CPU for single core case is shown in expression (2.1) – (2.4) (Expression (2.2) is calculation for static reconfigurable CPUs and expression (2.3) is calculation for dynamic reconfigurable CPUs). We remark on one important fact of CT before moving to multicore case. The CT would not be steady for both dynamic and static reconfigurable CPU. In other words, the time is dependent on the type of architecture we implement, and information we process during the period we are interested in. Also CT is measured as the average time obtained from tremendously large samples, since the instruction is not always executed in the same length of time. # 2.1 # 2.2 # _ __ # 2.3 # 2.4 where CT is Cycle Time, CTSI is Cycle Time for the Specific Instruction, dif is different, inst is instruction, TCT is Total Cycle Time, RP is reconfiguration Penalties, recon is reconfiguration, t is time, and ex is extra 9 As we see in expression (2.1)  (2.4), we have several different terms in reconfiguration penalties. Extra time to find the optimized configuration in the controller unit is usually longer than the benefit of reconfiguration. Therefore the dynamic system might have several cases that end up with worse performance in term of total CT compared to the static system, due to the reconfiguration penalties. As a result, the average total amounts of information that the system can process in the given time interval cannot produce outstanding benefit from reconfiguration. For the single core operation, the dynamic reconfiguration would not have sufficient motivation to implement, since it might not produce enough benefits in term of processing power as described above. Next we evaluate multicore reconfigurable CPU briefly. If reconfiguration of cores in systems has dependencies in terms of processing information, which means that all cores in systems cannot process information during reconfiguration, the result of simple observation would be similar to the conclusion from observation of single core case. Therefore we need to develop a new system whose reconfiguration of each core is independent of each other. In other words, the remainder of cores, which would not reconfigure, can still execute information during the process of reconfiguration. In this situation, the dynamic system equation in expression (2.1)  (2.4) cannot be used to determine total CTs. We have to determine reconfiguration penalties with more complex equations such as expression (2.5) and (2.6). The complexity of calculation increases tremendously, even though expression (2.5) and (2.6) look like simple equations. So we cannot determine benefit of reconfiguration as easy as evaluation of single core case if we use CT as performance measurement. 10 # 2.5 # # 2.6 2.1 Problem Statements From the previous argument, we need to develop new performance measurement, which we can easily use to determine the characteristics of dynamic systems and to compare the results with several different systems to find a better one. Also new measurement should be able to apply for static systems to compare performance between dynamic systems and static systems. As we discuss about performance of architecture, we not focus on the silicon area that is necessary for a whole system. We set our focus on processing power of systems. To determine processing power of systems, we cannot forget about one fact: results of performance measurements are dependent on benchmark programs we choose. For example, a result from one performance measurement shows outstanding benefits for a specific architecture, but the other performance measurement displays poor abilities for the same architecture. These differences come from the fact that different benchmark programs have different sequences of instructions, different measurement techniques, and different purposes of measurements which they are specialized for [10] – [13]. As a result of such specialization, we usually need to use several different performance measurements to determine benefits for implementing a where CT is Cycle Time, CTSI is Cycle Time for the Specific Instruction, dif is different, inst is instruction, TCT is Total Cycle Time, RP is reconfiguration Penalties, recon is reconfiguration, t is time, and ex is extra 11 specific architecture. Also most benchmark programs are developed for conventional computer system, which might not be as dynamic as we propose. Some of the bench mark programs might be developed for reconfigurable computers, but we would not measure performance of brainlike computers easily with them. This is because our proposed system has more flexibility to adjust system configurations and architectures dynamically to purpose of systems. As we describe previously, our brainlike computer is changing architectures according to the information we need to process while the machine executes the information. Therefore a result of performance measurement might not be always the same, since processing of information would change as we run the system. From this point of view, we need to develop the new measurement method that we could use for our purpose. In the previous paragraph, we emphasize the importance of developing new performance measurements for reconfigurable systems to compare each individual system configurations. We also need to develop a performance measurement for reconfigurations or performance prediction. Performance prediction has the huge impact on final overall system performance measurement. The reason of the importance of performance prediction comes from the fact that the optimization technique decides timings for automatic reconfiguration and candidates for next configuration based on the information obtained from performance prediction. Also the optimization technique is critical for our system. The relationship between control algorithm and performance of systems can be explained with analogy in a branch prediction. If branch prediction has great precision, the performance benefit from branch prediction becomes more obvious compared to systems without branch prediction. In automatic reconfigurable system, the 12 system with poorly developed optimization algorithm demonstrates only poor performance compared to the static systems. On the other hand, we can observe superior performance of dynamic automatic reconfigurable system from systems with welldeveloped optimization algorithm. Therefore control algorithm, its decision criteria, and performance prediction need to be developed carefully to obtain the sufficient results. As we close this section, we summarize the problems obtained from our observation in Figure 2.1. With these problems in mind, we go over proposed brainlike system and its assumption in the next chapter. Figure2.1 List of Problem Statement we will solve to create the proposed system • What kinds of evaluation technique or bench mark will we use? • What kind of performance prediction will the optimization algorithm use? • What kind of optimization algorithm will we implement for the system? • What kind of performance measurement will we use for the system? 13 CHAPTER 3 RECONFIGURABLE MULTICORE SYSTEM WITH GENETIC CONTROL 3.0 Assumptions Before describing the general idea of our system with optimization technique and simulation technique we implement, we introduce several assumptions we use for this study. These assumptions are used efficiently to decrease the number of small problems and to reduce the complexity of problems in simulation of our system. 3.0.0 Configuration constrains There are two methods that we can use to find architecture configuration or design in reconfigurable computers. One of the methods is that we start designing the computer configuration from scratch. We design the candidate architecture with all aspects, such as number of gates logics and functions implemented in the architecture, without any previous information and any design constrains except the maximum number 14 of gate available in a reconfigurable core. This method can find the best architecture candidate in terms of performance for a specific purpose. Even for the single static core system, the search space of architecture configuration would be tremendously large since we have infinite choices. As a result, the search time that is necessary to find the best architecture would take more than a life time if we implement any search algorithm without blueprints. This search time issue would cause more serious problems for dynamic multicore system. The search time that is necessary to find next configuration of each cores would take longer than a life time of production. The time needs for the search become too long for any numbers of cores if we do not use appropriate design constrains or predesigns. Since all system change processing information as time goes, the “best” configuration of the past moment would not produce sufficient performance benefit if the search time is too long. In the other words, there are some opportunities that performance of system after reconfiguration would be worse than the performance of system prior to reconfiguration. This is caused by the “inappropriate” change of system architectures. As we describe about reconfiguration penalties in expression (2.3)  (2.4), search time to find the next configuration for all cores should include evaluation of performance measurement. In dynamic system, each core would be redesigned to find better performance for each chance for reconfiguration. Therefore if search time is too long such as the time necessary to find the next configuration from scratch, the performance benefits from reconfiguration also diminishes. To reduce search time, we might be able to use the current designs or configurations of architecture as the start point of design. Such kinds of information might help to reduce search time that is necessary to find next configurations, but we 15 cannot guarantee that the previous configuration would be efficient starting point for the architecture designs if we adjust systems for processing information in current time. We can verify this fact with a simple example. Assume a simple system which is processing “information A” for a long time and current configuration optimized to process “information A” as “configuration M”. If “information A” changes to “information B” which require similar set of instructions to process, “configuration M” would be a sufficient starting point to improve performance. However, the opposite case would cause a different result. “Configuration M” would not be worthy of use if “information A” changes to “information C,” which requires completely different pattern of instructions compared to the instruction pattern necessary to process “information A”. In the two previous methods, we cannot have any characteristic information for each candidate we evaluate to find the optimized candidate beforehand. Therefore we should measure performance of architectures after the design is completed. To compare the candidates of next architecture configuration in the optimization algorithm, we need to wait until several other candidates are designed and measured. We can reduce the time necessary for multiple candidate designs by making the design process as simultaneous operation instead of sequential single design process. However, even with such kind of systems we cannot reduce the time necessary to complete any single candidate. Therefore these methods are not appropriate for our dynamic system. The reconfigurable computer with predefined configuration is the method we use. This method has several benefits that increase the performance of our system. The first benefit is that the performance increases from reduction of the time necessary to design core architecture. Since we only use architectures that are preconfigured, we do not 16 have to spend time for designing better architecture from the beginning. This idea is similar to the method of hierarchical design of Very Large Scale Integrated chip (VLSI) [14]. In the VLSI, we use the predesigned cells to create a larger and more complicated circuit. The cells used in the VLSI designs are extensively measured and welldesigned to be specialized for certain objectives. In our system, we use welldesigned architectures which are implemented in reconfigurable cores. As we describe at the end of the previous paragraph, we only use welldefined core architecture which we know all performance characteristics such as power consumption, processing power, and Silicon area necessary to create. This fact generates several other benefits. We can reduce reconfiguration penalties due to the performance measurements of the next configuration candidates. We would know maximum performance of each architecture configurations without any assumptions since we can evaluate performance prior to use. We can also calculate the maximum performance of a multicore system with simple arithmetic from the single core specifications. This wellestablished knowledge of performance can reduce the complexity of the optimization algorithm and the work load to find better configurations in the algorithm. In other words, the optimization algorithm is too complicated and time consuming without any prior knowledge of characteristic information since performance information is necessary to find better candidates. The reduction of reconfiguration penalties with preconfigured and welldefined systems are related to improvement in the processing performance. We go over one more benefit that is related to cost of implementation. Since we only use preconfigured architectures that we have the possibility to use, we can reduce the size of each reconfigurable core to the minimum requirement which is necessary to implement 17 the largest architecture we have. This benefit is related to the cost of Silicon area that is required to implement each core. If we are designing the architecture of a core from scratch, we cannot obtain the information for the minimum size requirement which might be used in our system. Therefore we have to prepare overhead areas up to the limit of the Silicon area we can use, and sizes of the reconfigurable core would be more than the necessary area, even though the size of the final configuration might be much smaller than what we prepare as the overheads. Table 3.1 displays comparison between two methods: designing from scratch and using the preconfigured designs. Table 3.1 Comparison of two methods of reconfiguration RP stands for reconfiguration penalties With Scratch With Preconfigured Designs Performance Without RP (Static) Better Worse Time Necessary to Create Next Candidate Longer Shorter Time Necessary to Evaluate Next Candidate Longer Shorter Complexity of Optimization Algorithm More Complicated Less Complicated Performance With RP (Dynamic) Worst Better Silicon Areas Used for each Design Cannot be determined prior to complete designs Can be determined with characteristics of designs 18 3.0.1 Data centric approach One of the performance measurements we can use is processing power of computers. This is one of the traditions we use in research of computer architecture. In general, we use throughput which described the number of instructions we can process in a given interval, the Instruction per Cycle (IPC), the Cycle per Instruction, and time necessary to complete specific instruction sets [9]. These measurements are focused on the number of instructions and the time needed to use the resources. There is other approach which uses data instead of individual instructions [15], [16]. This performance measurement uses the number of data or information processed in a given interval. Our brains always process several different sets of information in our daily lives. For example, the brain processes information from eyes to create what we feel to “see” such as colors, dimensional aspects, textures, and distances of objects. Also our brains process multiple sounds and identify the necessary information at the same moments. This identification comes from frequencies, amplitude, and distance from sources. If you think about motion of hands to grab something, human brains also process several different sets of information to move hands as we think. Therefore as we emulate flexibilities of the human brain, it is natural to use data centric approach for our system to find better candidates. If we consider more details of such information sets, we might consider them as millions of small instructions that have many dependencies. To reduce the effects of dependencies, we not break them down to individual instructions; instead we treat them as a set, which we define as inforuction from this point. Since we use inforuction for finding the next candidate architecture configuration, our data centric approach needs to define several different types of inforuction to create the performance 19 measurement details. Using these types of information, all preconfigured architectures are measured with their characteristics such as the amount of inforuction they can handle in a given time interval. In other words, we know all performance measurements in term of the processing power of inforuction. 3.0.2 Inforuction Buffer If we refer to architecture of superscalar processors in [9], we have an instruction buffer which stores instructions temporary till they feed to each individual pipeline. This mechanism allows us to control the flow of instructions and to utilize each pipeline as much as possible. We implement a similar mechanism in our system, which is identified as inforuction buffer. As we decide to use data centric approach, inforuction buffer stores each type of inforuction in different buffers. So each time inforuction is prefetched, the inforuction is separated with types of inforuction and feed into the corresponding inforuction buffer. The inforuction in the inforuction buffer is processed in the order they are fed in, which is the same order as firstin and firstout (FIFO) operation. This order reduces probabilities that we have dependencies among information. Therefore the inforuction buffer controls the flow of information and utilizes each core as much as possible. 3.0.3 Brief idea of architecture of proposed system The General concept of our system would be similar to a cell processor [5] or similar to a tree. Therefore we explain our system architecture with an analogy to a tree. For a tree, we have one big trunk which holds minerals, some nutrients, and water 20 obtained from the roots. Then the trunk sends these substances to the branches. The branches have different number of leaves that can implement photosynthesis, which uses sunlight to convert some nutrients and water and carbon dioxides into oxygen and some useful nutrients. Each leaf has also different amounts of chlorophyll which determines the capability of photosynthesis in a given day. In our system, the trunk corresponds to the inforuction buffer, the number of leaves on a branch corresponds to the number of cores in a system, and different amounts of chlorophyll corresponds to different architecture configurations we implement. Therefore our system has one big information buffer which stores and sends the inforuction to each core at the certain time and each core has input and output port at the same location in the architecture design. Therefore we can switch configurations of cores without any connection problems. 3.1 Optimization Technique In this section, we introduce the genetic algorithm as the optimization technique. The genetic algorithm is one of the newly developed field and one of the hottest topics in research of computational intelligence. Application of genetic algorithm to research of computer architecture is not new. The algorithm is used for research of VLSI design to find the optimized area and optimized number of VIAs for the situation [17] – [21]. These references and [22] give more details for genetic algorithm which we do not go over deeply. In this study, we only provide the minimum knowledge to understand operations of the genetic algorithm. 21 3.1.0 General Genetic Algorithm: Background information The genetic algorithm is inspired from mechanism in the natural world [22]. As we try to emulate flexibilities of a human brain with multicore processors, the genetic algorithm emulates the optimization mechanism of species such as natural selection, evolution, and mutation. In the natural world, we know that there is natural selection and theory of evolution, which are proposed by Charles Darwin. The natural selection theory tells us that the species with characteristics more suitable to environment will prosper, and the species which cannot survive in the environment will decline in number, and will be terminated eventually [23]. The evolution theory tells us that the species would change its characteristics based on environment through generations [23]. These two theories can explain as we go over the history of Earth. For example, the dinosaurs prospered in a certain time in the ancient earth, but they do not survive in the current era. There might be several different hypotheses for reasons of termination, such as climate changes due to strike of large meteor, and survival races with the small size Mammal species that started to prosper. All of those hypotheses tell us that there might have been dramatic environmental changes in the ancient era and the dinosaurs could not adjust their characteristics to the changes in the environment. There is another mechanism which keeps the varieties of species. In the natural selection mechanism, each species would converge to the optimized characteristics, but the other mechanism generates the diversity in the species. This mechanism is called mutation. With mutation, the genes of the offspring generation would have different traits from the parent generation. We introduce several terms which are commonly used in the genetic algorithm prior to going over the operations of the genetic algorithm. Most definitions that we use 22 come from [22]. To implement the genetic algorithm, we need to decide the targets of optimization and how we evaluate systems with the objective we define. The targets of optimization are anything that can be evaluated with numeric values from distance of travels in the Traveling Salesman problems (TSP) to areas and numbers of VIAs in VLSI designs [21] [24] [25]. The method of evaluation is called the fitness function and numerical values obtained from fitness functions are called the fitness values. The numeric data of fitness values represents quality of measurement of the objective. To establish the fitness function, we also need to decide how we represent systems with some DNA like combinations, which is called chromosome. In other words, chromosome is representation for a possible candidate configuration of a whole system. Each entry in chromosomes represents some traits of a system, as each set of entries in DNA represent some kind of characteristics. For example of TSP, chromosome is the traveling path which travelers will follow to visit necessary cities, and the entry in chromosome or gene corresponds to a specific city which he has to visit. Set of multiple chromosomes is called population. At the initial stage, general genetic algorithm produces a set of chromosomes up to population size which is defined by designer, and would not change the population size for the entire algorithm. We usually use random generation method, in which each gene in chromosomes is set randomly to include various chromosomes in population. We identify these initially generated candidates as population of the first generation. After we set population, we pick up parents of offspring with some methods such as random, weighted random, and other methods. With chosen parents, we use some methods to create set of offspring. One of the commonly used methods in process of offspring 23 generation is called crossover. With the crossover operation, children have some common pattern of genes from both parents. As the name implies, crossover generates the offspring by exchanging some gene pattern between parents which is similar to mechanism of gene pattern succession in the offspring. Example of crossover is displayed in Figure 3.1. After generating a candidate or candidates of next population, we implement the mutation operation. This changes part of gene pattern randomly. Example of mutation is also displayed in Figure 3.1. Then we evaluate generated offspring and old generation with fitness functions. With fitness values and superiorities of fitness values that we decide, we sort entire set of chromosomes which contains both offspring and the entire population of previous generation. Then we implement termination mechanism to adjust the number of chromosomes in the population to the size of population we decide to use. After creating the new population, we designate this set as population of the second generation. In other words, we increment generation number each time we create new population. The processes after production of population of the first generation are repeated continuously till certain conditions are achieved. This condition is identified as stopping criteria. Examples of stopping criteria are optimized candidate have sufficient fitness value or maximum generation we define is passed. Figure 3.2 shows a flowchart of the genetic algorithm. The term iteration is used to count the number of repetitions for the entire flowchart in Figure 3.2. 24 Figure3.2 Operation flowchart for the genetic algorithm Start Initialization Generation Evaluation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the chromosome randomly 2.) Generation Stage a. Choose the parents b. Implement Crossover c. Implement Mutation 3.) Evaluation Stage a. Evaluate with Fitness function 4.) Termination Stage a. Sort the population with result of 3‐a.) b. Choose the chromosome to terminate c. Generate new population 5.) Check Stage a. Check for stopping Criteria Figure3.1 Operation of the genetic Algorithm A C E A E B A B C B A E A.) Cross over operation with multiple offspring case A B C A E B A C E B A E A C E B A E A C A B A E B.) Mutation operation 25 There is significant benefit for applying the genetic algorithm as the optimization technique. The genetic algorithm is an optimization algorithm which has both global search and local search abilities. With the crossover operation, we implement the local search. With mutation operation, we implement the global search, which checks randomized candidate other than similar candidates which we produce with crossover. In conventional optimization algorithm, most algorithms have only one search method, not both. Also the conventional optimization technique uses the sequential evaluation, in which the algorithm generates only single candidate, evaluates and compares with the current system. Example of sequential optimization is simulated annealing [25]. For the genetic algorithm, we use the parallel optimization, which generates multiple candidates, evaluate, and compares with the previous population. We can find better candidates more efficiently since we check more candidates simultaneously and choose better candidates. In this section, we discuss the general genetic algorithm. As we close this section, we define two terms: global optimum and local optimum according to [23]. The local optimum is better candidate than all other candidates in terms of fitness values among results of the current search. The global optimum is best candidates among all other local optimum in terms of fitness values. Relationship between these optimums is similar to cost of gas in a certain state. We can find cheapest price of gases in a city when we compare prices inside a city. This cheapest price or local minimum might not be cheapest price all over the state or global minimum since we might find better result from another city. This terminology would be used in this section. In next section, we go over the genetic algorithm that we implement in our system 26 3.1.1 Specialized General Genetic Algorithm In the previous section, we introduce background information for the genetic algorithm. The actual genetic algorithm that we implement in our system has more functions and is slightly different from the general genetic algorithm. In this section, we describe the characteristics of the specialized genetic algorithm. 3.1.1.0 Dynamic population As we explained in the previous section, the basic genetic algorithm has a fixed size of population which is not changed for the entire algorithm. The choices of appropriate size of population are one of the hottest topics in research of genetic algorithms. The reason is that the size of the population is deeply related to abilities of the optimization and time necessary to complete the search algorithm. We can explain this with a simple example. Assume we have the genetic algorithm which implements a fixed number of generations. If we increase the size of the population, the possibilities to find optimized candidate or the best candidate would be greater than with smaller sizes, but calculation costs of each generation would also expand. On the other hand, if we reduce the size of the population, calculation costs will get smaller but, the possibilities to find the best candidate will also decrease. In our dynamic system case, we want to reduce the calculation cost as much as possible, but at the same time we want to increase possibilities to find better candidates as much as possible. So the determination of a good population size is too sensitive of an issue since the choice of the population changes the functionality of algorithm dramatically. To overcome issues related to finding the best population size, we use the dynamic population size approach instead of the fixed 27 population size as [26]. With this approach we start from the relatively smaller initial population size which we define. After the genetic algorithm starts, we do not know the population size since the size is automatically adjusted according to the current condition of the optimization process. There are several characteristics we have to define for the dynamic population approach. Those characteristics are what would be the trigger of change the population size, how we will change it, and how much we will change it. If we do not choose each category carefully, the dynamic population algorithm does not work correctly or simply works as the fixed size population approach. The first question we tackle is what would start the process of changing the size of the population. Since the dynamic population is part of the genetic algorithm which uses the fitness values to determine whether candidates are better or not, we can use the fitness values of the population to trigger changes of the population size. There are several different statistical data of the fitness values. Examples are the best fitness value, the worst fitness value, the mean fitness value, and the median fitness value of the population. Within these values, we use the average or mean fitness value of the current population and the mean fitness value of the group which consisted of both the current population and the candidates which we generated. This idea came from a question that was asked by then Ph.D. Student WenFung Leong during one of my course presentations. Since the average fitness value displays the performance of the optimization process as a whole in a given moment, the dynamic population would ensure proper resource management for the search ability of the genetic algorithm. Each 28 time we obtain the new fitness values of candidates and the new fitness values of the current population, we initiate the process of the dynamic population algorithm. As we decide when we will change the size of the population, we need to decide how we will change it according to the difference between two average fitness values. There are two different resource management strategies we can use to determine how we will change the population size. These two methods of resource management are similar to methods that students commonly use in their studying for final exams. Some students prefer spending more time for subjects that they are very good at, and spending less time for topics they hate. As a result, students would answer the question extremely well for the subject they studied and cannot answer the questions they did not study well. Or more simply, students become specialized in specific subjects they like. On the other hand, other types of students would spend more time on subjects which they are not good at and spend less time for the subjects which they feel strong in. These people use time where it is necessary to spend it. Comparing these two types of students, the second type of student has more chances to have better grade point average (GPA). This example is true among different disciplines. Back to method of resource management, we describe and evaluate two types of strategies for increasing the chance of generating better average fitness values. The first type of resource management technique uses more computational resources when we have better average fitness values and uses less when we have poor results. In other words, we spend more time where we find better average fitness values and less time for where we cannot find good average fitness values. This strategy might find a local optimum quicker than the other method, but one problem of this method is that the local 29 minimum we find is not always the global minimum as we describe at the end of the previous section. For the second strategy, we utilize more resources when we have a hard time to find the better average fitness values and less when we can easily find better fitness values. This method spends more time where we cannot find better average fitness values and less time where we find better average fitness values. The comparison of these two strategies in a real situation can be explained with an analogy of openbook/open note exam. Assume we try to solve two different types of questions: questions that we have enough knowledge to solve and questions that we do not have any idea how to solve. To solve the first type of questions, we only need to check the correctness of our memory with books to obtain better scores. In this case, we just have to use resources which relate to the concepts we need. If we just go over each topic in the text books, it is just wasting time and we will end up running out of time to solve the other questions. To solve the second type of questions, we cannot review specific topics since we do not have any idea how we can solve them. We have to go over each topic briefly to find any related concepts which can be used to solve the questions. If we randomly choose specific chapters in books to read in detail, the exam time is too short to find necessary information. The first method of taking exams demonstrates a similar situation as the case when we know the fitness value of the global optimum. This is not the situation where we are during the search, since we do not know what the global optimum is. Therefore, we have to apply the second strategy instead of the first method. In other words, we will increase population size when we have a hard time to find better average fitness values or very close to optimum (either global or local) and reduce the size when improvement in average fitness values is sufficient. In this 30 method, we would have better opportunities to find the global optimum. There is one problem while applying the second strategy: the population size might get too small to keep operation of the algorithm correct if we constantly improve the average fitness values. We discuss the solution for this issue in the latter section of this chapter. We have already decided the timing of change and the method of change, but we have not yet finished the argument for the degree of change in the population size. This question has also several different strategies such as the constant fixed change method, dynamic fixed change method and proportional change method. We briefly go over each strategy with problems and benefits. The first strategy is simple enough to implement, since the size of change in the population is defined at the beginning of the algorithm. Therefore, we do not have to change it and also we do not have to calculate the degree of change according to the improvement in the average fitness value. The problem of this approach is very obvious, the size always changes constantly no matter what the current size of the population we have, and how much we improve the average fitness values. In extreme example, a result of twentyfive percent improve in the average fitness value cause the same degree of change in the population size as a result of one percent decrease in the average fitness value. Also the impact of change does not take into consideration the change in the population size. If we only use a fixed number of candidates to change the population size, the impact of change would not be efficient when the size of population is large. For example, we would double the size of the population if we change its size from 10 to 20. However, there will be only ten percent of increase in the size of population if we change the size from 100 to 110. The impact of the changes in the average fitness value in the previous two examples is not the same. The second 31 approach requires several conditional statements to implement the algorithm, so the calculation cost will increase slightly compared to the first approach. The degree of changes in the fitness values are reflected in the second approach, but the impact of changes that is dependent on the population size is not included in this algorithm. The third approach treats both the degree of changes and the impact of changes. Instead of a fixed size algorithm implemented in the previous two approaches, it uses the proportional changes which are dependent on both the population size and the degree of changes in the average fitness values. The calculation cost for implementing the third method is slightly greater than the second approach. Even with the disadvantage in the calculation cost, the third approach is worth implementing, since we can change the population more dynamically compared to the other approaches. 3.1.1.1 Off by one theory We now explain the method we implement to avoid errors in the algorithm due to the reduction of the population size. Since we implement crossover operation, we definitely require at least more than two chromosomes in the population. The method is that we insert new sets of the chromosomes into the current population whenever the population size does not meet the minimum size requirement of the algorithm. New sets of the chromosomes are generated with some randomization mechanism. Before we explain randomization mechanism to fix violation of the minimum size requirement, we go back to several observations we discuss previously. In section 3.0.1, we describe that the current adapted core architecture configuration in the dynamic system would not guarantee good performance in the future. This statement is true when we observe processing performance of computer systems. For short time observation, we 32 can say that current configuration would produce sufficient performance to use as seeds of randomized chromosomes, since the contents of inforuction buffer changes slowly unless it is completely empty. Therefore the current configuration would offer several hints to find the next configuration. If we only add the same configuration to the population, the abilities of both global and local search would decrease. Therefore we need to generate randomized candidates from the current configuration. In the randomization process, we generate candidates according to the off by one theory. This theory tells us that it would be better to change the architecture of only one reconfigurable core in the randomization process. This theory is derived from the careful observation of the assumption we made earlier. We assume that during the process of reconfiguration the reconfiguring core cannot process any inforuction. Therefore, if we increase the number of core which reconfigure, it implies the number of cores that cannot process inforuction in several intervals. As a result, performance of the system would decrease significantly during reconfiguration. Hence, candidates that only change one core would yield similar performance as the current configuration of the system. In most cases, generated candidates would have less performance in the processing power due to the reconfiguration penalties. From this observation, we create candidates which randomize only single core from the current configuration, and we insert generated chromosomes into the population to prevent failure of the algorithm and to maintain diversity in the population. Figure 3.3 illustrates the flow of the modified genetic algorithm. 33 3.1.1.2 Multiple Crossover Operation with multiple parents There are several papers which study about the effect of multiple crossover operations in the genetic algorithm. Examples of such studies are [27] [28] [29]. The multiple crossover operators have one important benefit. This method enhances the global search abilities of the genetic algorithm. Even though the crossover operation implements local search, each different crossover operator would search through different search spaces. The variety of children in each generation would increase compared to the implementation of single crossover operation. Also, the multiple parents would increase the global search ability, since we choose several different sets of parents Figure3.3 Operation flowchart for the modified genetic algorithm Start Initialization Adjustment Evaluation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the chromosome randomly 2.) Adjustment Stage a. Change the population size 3.) Generation Stages a. Choose the parents b. Implement Crossover c. Implement Mutation 4.) Evaluation Stage a. Evaluate with Fitness function 5.) Determination Stage a. Evaluate the next population size 6.) Termination Stage a. Sort the population with result of 4a.) b. Choose the chromosome to terminate c. Generate new population 7.) Check Stage a. Check for stopping Criteria 8.) Stop Stage a. The best candidate is picked up as the output of algorithm Generation Determination Minimum size? Not Satisfied Satisfied 34 for each type of crossover operator. So many traits of chromosomes are effectively used to create the next population. 3.1.1.3 Fitness function In this section, we talk about the most important topic of the genetic algorithm. This is not an exaggerated expression since the result of fitness function is used for control of reconfiguration and control of the dynamic population. We go over several facts that are used to develop our fitness function. To compare each configuration of the system, we can use the processing performances of configurations after we complete the process of reconfiguration since they are simple enough to calculate. Even though we know the processing characteristics of each core which we obtain from measurements, the actual performance of cores and systems might be lower than what we calculate. There are three types of barriers that make system performance lower. One of the barriers is the stall. The stall is the time we cannot have the full abilities of processing power since some infoructions are not ready to process [9] or we have too much stock of inforuction in the inforuction buffer. This is caused by dependencies in inforuction. In the stall condition, systems cannot obtain any new infoructions. Another barrier has a similar effect as the stall, but the cause of this barrier is slightly different. We name this barrier emptyrunning. As the name implies, the system does not store sufficient amounts of specific types of infoructions in the information buffer compared to the maximum performance we have. We explain the problem of this situation with an example. We feed each type of infoructions into the corresponding inforuction buffer each time we prefetch. Each reconfigurable core in the system processes infoructions from this set of inforuction buffers. If we have sufficient pre 35 fetched infoructions for all types of inforuction buffers, the system can process as much as possible with its maximum potential and there is no problem for this situation. However, if the inforuction buffer contains fewer amounts of some types of inforuction, cores cannot utilize the fullprocessing power as we calculate. It can only process the amounts of inforuction in the inforuction buffer. After it completes processing, it becomes idle or runs with the emptied inforuction buffer till the next set of infoructions is ready. Another barrier is reconfiguration penalties. During reconfiguration, the processing power of systems decreases compared to full specification since several cores are isolated or excluded from our system. After reconfiguration, the isolated cores become active to process infoructions. Therefore these performance changes during the process of reconfiguration also make the processing power difficult to use as the fitness values of our system. With all three of these barriers together, we cannot use processing power directly to determine the fitness values of a given system configuration. The appropriate fitness function should treat all three barriers. We use the predicted amounts of infoructions we can process in a certain time interval as our fitness values. The detail of fitness function is described in expression (3.1). The time parameter t is used in expression (3.1). This time parameter should be longer than the reconfiguration penalties since we know the performance of a dynamic system during reconfiguration is lower than the system which stays the same as the current configuration. If we take a longer time interval for the parameter t, calculation costs of reconfiguration would increase dramatically since the fitness function emulates behaviors of systems to predict amounts of information we might process. To predict the 36 performance of dynamic systems, we have to predict the amount of infoructions which will be generated in the time interval t since the inforuction we need to process in the future time is unknown. # # # # 3.1 The approach we take for prediction of the future infoructions uses the similar concept in the neural network system [30]. In the neural system, we train the network with some sample patterns which model the operation of the system. The neural network trains to obtain the correct result or desirable results in terms of purpose of the system with the differences of simulated results, and preferable results. For our system, we will train our prediction mechanism with the data of the generated infoructions which are fed into our inforuction buffer whenever we do not reconfigure the system. Our training method is straightforward. We take the data for occurrence of each inforuction for a specific time interval. This time interval is related to the time parameter (t) we use in the fitness function. As a result of the fitness value evaluation, we conclude that we do not have to reconfigure our system, since the current system configuration might have better performance within the time interval (t). Therefore we might not have to reconfigure our system during the time interval. At the same time, we do not have to evaluate the candidates with the genetic algorithm. We use the time interval in which the 37 optimization process does not operate, and resources which is usually used in the optimization algorithm. We discuss the meaning of the data of inforuction occurrences in the later chapter. We will evaluate the impact of misprediction. The misprediction occurres when the data for occurrence does not correspond to the actual behavior of systems. It happens when sets of inforuction produced are changed dramatically from what we observe. The impact caused by the misprediction would not be severe since it is softened by the inforuction buffers. This is because the sets of inforuction in the inforuction buffer should be processed prior to the sets of inforuction predicted with the prediction mechanism. In other words, we always have some portion of infoructions that we will definitely process since they are the stored infoructions in the inforuction buffer. Therefore, the ratio of amounts of mispredicted inforuction handled in the fitness function to the infoructions that are predicted to be handled would be always less than 1. Even though there is a possibility of misprediction, our prediction mechanism represents the actual behavior of systems more accurately than the simplest prediction method, which assumes to have exactly the same number of each inforuction during our prediction. As we close this section, we show the flowchart of the fitness function in the Figure 3.4. Our fitness function is a short time simulation of the system since we need to determine the performance in the future for both types of systems: the system with the current configuration and the system with the candidate configurations during the process of optimization for the multicore system. 38 3.1.1.4 Running BEST The genetic algorithm will converge to the optimum when we use algorithms with a large number of generations. Hence, the algorithm needs long time to obtain the optimum. Even if we use large number of generations, the optimum obtained is either local or global. There is no guarantee we can get global optimum without prior knowledge. As we implement the genetic algorithm as part of dynamic system, the large generation for convergence would be problematic, since the larger generation needs more time to compute the fitness values. Therefore we cannot wait the algorithm to converge, and we should set the generation we want to use as the stopping criteria. Instead, we use Figure3.4 Operation flowchart for the fitness function Start Initialization Generation Processing Evaluation Time t passes? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Memorize the current inforuction buffer and current pattern of inforuction generation 2.) Generation Stage a. Generate the inforuction pattern the same as 1‐a.) 3.) Processing Stage a. Increment the internal clock b. Process the # of inforuction for the current processing power 4.) Check Stage a. Time check i. Check whether the time interval t is passed? b. Stall check i. Check whether the stall is happened or not 5.) Evaluation Stage a. Evaluate the fitness function Stall? Not happened happened 39 the running best or optimized candidate as our next candidate, which is the candidate with best fitness values that we evaluate through our algorithm. In other words, we stop the genetic algorithm with a specific generation, and obtain the best candidate from the given population. Since the chosen candidate is the best candidate in the population, we can use this approach for the best candidate that we can find within the limited resources. 40 CHAPTER 4 STATIC RECONFIGURABLE SYTEM: GENETIC ALGORITHM EVALUATION 4.0 Reason for static reconfigurable computer implementation Even though we have several examples which apply the genetic algorithm to research of computer architecture [17] – [21], we do not have an example of the genetic algorithm applied as the optimization algorithm to find better configuration candidates in terms of processing power of CPUs. We can prove the performance of the genetic algorithm to find the optimized candidates through the implementation of a static reconfigurable computer, which is similar to a cell processor. Also we can develop the framework of simulation that we can use for the dynamic system. In addition to these benefits, the results of simulation can be used as the performance of specialized static computer, which can be used to compare with our proposed system. Therefore we should implement a static reconfigurable computer. 41 4.1 Assumptions for Simulation We describe the important assumptions that are necessary for the simulation for the dynamic system in Chapter 3. We will discuss assumptions that we will use for the static reconfigurable systems and will introduce the new mechanism with a new assumption that would be used in both simulations of static and dynamic systems. Assume we have the multicore system described in section 3.0.3. Each of architecture configurations of cores we use in our system is well designed. The characteristics of each architecture configuration are well measured in terms of amounts of possible inforuction each core can process during a certain time unit. This measurement is called Inforuction Per Clock Cycle (IPCC). Since we implement superscalar architecture in each core, IPCC for each core has amounts of each types of inforuction that a single core can process simultaneously during a given time unit. Before discussing the details of genetic algorithm in the next section, we will introduce the new concept: stochastic inforuction generator. 4.1.0 Stochastic Inforuction Generator Before introducing the stochastic inforuction generator, we will go over the basic idea of stochastics. Most definitions come from [31] – [33]. When we observe result of a fairsixfaced dice roll, we get faces from 1 to 6. For short time observations or from small number of samples of a single dice roll, occurrence of each faces dynamically change as we roll, and we cannot find steady result in frequencies of occurrence for each face. When we observe fairly large numbers of dice roll or we have sufficient numbers of samples of dice roll, there would be steady data for occurrence of each face, which is 42 one sixth for each face in this case. In other words, if we observe some system for a long time, we would find stochastic data or probability information in behaviors of the observed system. In the previous example, the stochastic information we get is frequencies of occurrence of each face. Since this is the representation of system behavior, we can predict the behavior of the given system with probabilities. The example of prediction is probability of faircoin toss. We know probabilities of occurrence for each side of the coin would be one half. Therefore, if we toss a coin significant number of times, we can predict that we will have about half of toss as heads and the other half as tails. In real situations, there are dependencies among occurrence of each instance. Since the dependencies change the probabilities of occurrence, our prediction of occurrence is more difficult. However, if we find out all dependencies, the predictions would correspond to the actual system behavior. If we observe a single computer system with a certain simulation for a long time, or if we observe multiple computes with same settings, there should be stochastic information for occurrence of each type of instructions. We prove this statement with contradiction. Assume we do not have any stochastic information or probabilities for occurrence of each instruction. In other words, the instructions we process is decided randomly. For such situation, we cannot reproduce a result of simulation, even if we use the exactly same setting. However, the normal simulations implemented in some benchmark programs definitely have steady results that we can reproduce with the same settings. With reproducible results, we justify our accomplishments. Simulators or benchmark programs are designed to reproduce the data if we use the exactly same setting since they produce the same sets of instructions for the same settings. On other 43 hand, if we have different sets of instruction, the result of simulation would not be reproducible. This is contradictory to what we assume: we cannot reproduce the same result since the instruction is randomly generated. Therefore there exists the stochastic information for patterns of instruction generation in a simulator, which is dependent on the type of application. This assumption is based on the observation of a specific purpose application. For example, the mathematical application software would produce more instruction related to mathematical operation compared to other software. If we are watching a movie on the computer, the instruction related to graphics and sounds would be more than the normal operation of the system. For our system, we would have stochastic patterns in inforuction generation that are different for each types of application. With stochastic information for occurrence of each types of inforuction, we can generate infoructions to simulate real behavior of systems. We call this stochastic method of generating inforuction as stochastic inforuction generators. We will remark one more fact for the stochastic inforuction generator. The stochastic information should obtain from data that is consisted of large numbers of samples since validity of the stochastic information increases with larger amounts of data due to the reduction of the effect from the noise or unexpected data. Also we need to use stochastic inforuction generator for longer cycle to increase accuracy and precision of the simulation. The actual process of inforuction stream generation is illustrated in Figure 4.1. As Figure 4.1 displays, we use a random number generator to generate the actual inforuction in each cycle. We cannot match the stochastic information used to the generate infoructions with the stochastic information from actual generated infoructions in each cycle. We can only observe the random generation of infoructions in a short time. 44 However, if we observe the inforuction generation pattern for a long time, we can get similar stochastic information as information used to generate inforuction stream. From this point, this method can be used for a short cycle operation, which does not have any clear stochastic information for a generation pattern. Figure4.1 Operation flowchart for the inforuction generation for each cycle 4.1.1 Dependencies and inforuction stream Up to this point we do not have any mechanism to implement for dependencies of infoructions. For our simulation, instead of implementing the actual dependency mechanism, we randomly insert an extra cycle in which no new data is fed into the inforuction buffer. This corresponds to NO OP instruction in regular computer terminology. To model system accurately, the numbers of dependencies correspond to the Start Load stochastic Set Ref Check the type Stop 1.) Load Stage a. Load stochastic data of inforuction generation 2.) Set Ref Stage a. Use random generator to set the reference point 3.) Check Type Stage a. Check what type of inforuction will be generated (Find the value k which satisfies the following expression: Σ Pith type ) 4.) Generation Stage a. Generate the inforuction according to check stage result 5.) Check # of Generated Stage a. Check the number of inforuction generated for this cycle is the same as the number we defined or not Completed Not Generation Generate all? 45 numbers of total inforuction we will process in our simulation. To compare the systems with the same number of cycles fairly, we use the exact same inforuction stream. This means we have the same stochastic data, the same number of inforuction, the same numbers of dependencies, and the same sequence for each inforuction. 4.2 Genetic algorithm for the static operation The genetic algorithm we implement for the static system has the same characteristic as dynamic algorithm expect the several differences that come from system properties. For the static application, we do not change system configuration while the system processes infoructions. Therefore we do not have to worry about reconfiguration penalties and reduction of performance due to reconfiguration. The objective of the static reconfigurable computer is to find the optimized configuration for the system which has the “best” performance for given application or application sequence. So fitness values of the static reconfigurable computer are the total time unit necessary to complete all inforuction. As we describe previously, we have to worry about the reduction of processing performance due to stall and emptyrunning, since stall and emptyrunning will increase the necessary time unit to complete all inforuction. The flowchart of the static genetic computer is described in Figure 4.2. We go over several stages which is different from the dynamic operation we described at the previous chapter. 46 Most significant difference between dynamic operation and static operation is location of the genetic algorithm or the stage of simulation. For dynamic systems, we are running simulation while we use the genetic algorithm to find better candidates of the next configuration. For this application, we run the miniature of simulation in the process of fitness function evaluation. For the static operation, we use the genetic algorithm after we simulate a system to find the fitness values. The details of simulation flow are shown in Figure 4.3. Figure4.2 Operation flowchart for the genetic algorithm for static operation Start Initialization Adjustment Simulation Termination Stopping criteria? Satisfied Not Satisfied Stop 1.) Initialization Stage a. Create the configuration of cores randomly 2.) Adjustment Stage a. Insert randomly generated candidates to satisfy the minimum population size 3.) Generation Stages a. Choose the parents b. Implement Crossover c. Implement Mutation 4.) Simulation Stage a. Simulate the time necessary to complete the inforuction sets 5.) Determination Stage a. Evaluate the next population size 6.) Termination Stage a. Sort the population with result of 4‐a.) b. Choose the chromosome to terminate c. Generate new population 7.) Check Stage a. Check for stopping Criteria 8.) Stop Stage a. The best candidate is picked up as the output of algorithm Generation Determination Minimum size? Not Satisfied Satisfied 47 This figure is similar to Figure 3.4 which displays the flow of fitness function in dynamic systems. The differences between these two flowcharts are at the last conditional or check statement. For the fitness function of dynamic system, the amount of infoructions processed is variable, and the cycle in which we simulate remains constant. The simulation for static systems is targeted to obtain the difference in time cycle for given amounts of infoructions we need to process. From these reason the stall condition is implemented in the different location in the two flowcharts. Another difference between the two flowcharts is the method we use to generate chromosomes to adjust the population size. Remember for the dynamic system, we introduce the offbyone theory, which tries to change configuration of only one core in Figure4.3 Operation flowchart for the simulation stage of genetic algorithm for static application Start Generation Processing Stall? Not Happened Happened Stop 1.) Generation Stage a. Generate the inforuction pattern which is pre‐configured for the purpose for the system 2.) Processing Stage a. Increment the internal clock b. Process the # of inforuction for the current processing power 3.) Stall Check Stage a. Check whether the stall is happened or not 4.) Information check a. Check whether all inforuction is completed or not Complete? Completed Not completed 48 the process of generating the extra candidate for adjusting population size. This theory is to avoid the severe reconfiguration penalty from reconfiguring multiple cores at once. As we described previously, we do not have to worry about the reconfiguration penalty in the static system. Therefore we insert chromosomes which are randomly generated to ensure the varieties in the population. Since there are local optimum issues for the optimization process, the randomly chosen configuration would give more chances to find global optimum. One more remark for simulation method we can use for both dynamic and static system as we close this section, which is how we implement the stall. As we describe, the stall is time necessary to “catch up” with the current inforuction flow to avoid the hardware hazard. Therefore the stalls are detected when any types of inforuction buffers have greater amounts of infoructions than the dimension we predefined. During the stall, the internal clock is incremented without generating new inforuction sets. The stall will be continued until amounts of infoructions in all types of the inforuction buffers are smaller than the limitation we defined. In the next section, we will go over the simulation setting and results of the simulation with observations. 4.3 Simulation settings and simulation results In the previous section, we go over details of the genetic algorithm for the static reconfigurable CPUs. Before we show the results of simulations, we go over the details of the simulation setting. 49 We simulate our programs with 77 high end computers simultaneously to reduce the simulation time. Performance of each individual computer which runs simulation is given in Table 4.1. In our simulation, we have two types of settings. One of them is common for all static computer simulations and the other is unique for each individual simulation. We go over the details of common characteristics and then describe details of unique settings. Table4.1 Performance of Simulation Stations Performance Cumulated # of computer 77 CPU Intel® Core™2 Duo Processor 6700 @ 2.66 GHz Memory 2 GB We choose the following setting as common configuration for all static computers: number of different types of inforuction, characterization of each type of infoructions, amounts of infoructions generated in a time cycle, number of predefined architectures we use, characterization of each core architectures, number of generations in the genetic algorithm, and number of initial population. Also we set the number of maximum population we will use in the genetic algorithm as constant to improve the simulation time. We identify 4 different types of infoructions that we use to characterize the performance of core architecture and stochastic data in inforuction generation pattern for a certain application. The types of infoructions are similar to types of functional units in the superscalar processor [9]. The types of inforuction are logic, mathematic, floating point, and memory. We use 4 different pseudo applications that have unique stochastic information pattern for each inforuction. Each of application is identified as General, 50 Logic/Math, Floating Point, and Memory, which corresponds to the intensity of the infoructions for a given application. Characteristics of each application in terms of stochastic data of inforuction generation are summarized in Table 4.2. We define the characteristics of 5 different specialized cores. We name each type of architecture such as GENeral, LOGic, MATh, FLoating Point, and MEMory, which corresponds to their specialization. The performances of each type of architecture in terms of IPCC are listed in Table 4.3. The total amounts of inforuction each processor can handle are set to 8 which is the realistic number since it corresponds to the number of functional units in the superscalar processor [9]. To emulate changes of application in the systems, we randomly choose three applications from the repeated sample which consisted of the four applications we defined. The list of all inforuction generation patterns is displayed in Table B.1 and Table B.2. The common characteristic of systems we simulate is set as Table 4.4. Each inforuction stream is unique for the same length of cycle for each application we want to simulate. Table4.2 Stochastic data of Inforuction generation in the percentage where L is Logic inforuction, MA is Mathematic infoructions, FLP is Floating point infoructions, and ME is Memory infoructions. L MA FLP ME General 35 30 20 15 Logic/Math 70 18 7 5 Floating Point 5 12 80 3 Memory 15 15 10 60 51 Table4.3 Amounts of inforuction that each architectures can process in the given time unit where L is Logic inforuction, MA is Mathematic infoructions, FLP is Floating point infoructions, and ME is Memory infoructions. L MA FLP ME General 3 3 1 1 Logic 4 2 1 1 Math 2 4 1 1 Floating 1 1 5 1 Memory 1 1 1 5 Table4.4 Common setting for each configuration in simulation Setting # of total simulation 64 ( = 4^3) Total # of Inforuction prefetched 64 Size of Initial population 15 # of generation 200 Maximum size of population 450 (= 15*30) Dependencies factor .05 The rest of the settings, such as the number of reconfigurable cores we have in a system, the number of minimum cycles for each application, the number of iteration we implement, and the amounts of inforuction that trigger stall, are chosen to be variables to observe the properties of the static reconfigurable CPUs. Each individual setting for these variables is shown in Table 4.5 and the complete set of actual setting for each system we will simulate is in Table B.3 through Table B.6. 52 Table4.5 Variables and their possible settings Candidates of setting we will setting # of cores in the system 2, 4, 6, 8, 10, 12, 14 Length of each application 50, 100, 200, 400, 600 # of iterations we implement 10, 15 Stall trigger 30, 50 4.4 Simulation Results and Observations Our simulation time to complete individual configuration over 64 different application sequences are less than 5 minutes with the computer we used. Before discussing about any further observation of results, we discuss how we will compare the results of simulations among the different settings. We use a PITCGEN (Percentage of the performance Improvement in terms of Time necessary to process all infoructions Compared with the performance of GENeral core only systems) to describe the performance of our systems. Remember, our raw simulation result is time necessary to complete the inforuction streams. To obtain the performance improvement compared with the general core only system, we use the expression (4.1). We identify these ratios as a Specific PITCGEN (SPITCGEN) since these measurements are dependent on the types of application sequences in the simulation. To find the Average PITCGEN over all application sequences (APITCGEN), we use the expression (4.2). The result of the 53 calculation of APITCGEN is shown in Table 4.6. We should not forget that SPITCGEN and APITCGEN are both dependent on the setting of the systems. 1 4.1 Σ 4.2 Figure 4.4 and Figure 4.5 (Enlarged figure is in Appendix: Figure B.1 through Figure B.6) displays the APITCGEN for BEST (BEST performance we find in the whole algorithm), AVER (AVERage performance of the best performance we find in each iteration), LOG (LOGic specialized core only systems), MAT (MATh specialized core only systems), FLP (FLoating Point operation specialized core only systems), and MEM (MEMory operation specialized core only systems). Figure4.4 APITCGEN for different types of systems Left graph: result of BEST and Right graph: result of AVER. The horizontal axis displays different settings: S001 through S077 which is depicted in Table B3 through Table B6. 54 Figure4.5 APITCGEN for different types of system Top Left graph: result of LOG, Top Right: result of MAT, Bottom Left: result of FLP, and Bottom Right: result of for MEM. The horizontal axis displays different settings: S001 through S077, which are depicted in Table B3 through Table B6. Figure 4.4 and Figure 4.5 demonstrate that we seem to have about 30 % improvement in overall performance compared to GEN. This performance increase comes from the result of the static reconfiguration according to the individual inforuction streams. Since we have a different configuration for each inforuction stream, we can compare our result with the best configuration for single design core only systems. To compare the performance of our system with the best performance for single design core only systems, we use expressions (4.3) and (4.4). Since GEN systems do not produce the best PITC for all settings, this comparison provides more information about the optimization capability of our system. 1 4.3 55 Σ 4.4 Figure4.6 APITCALL with BEST for different types of systems Figure4.7 SPITCALL with BEST among systems Each entry in the graph corresponds to a specific setting (S001 – S077) in Table B.3 through B.6. 56 Figure 4.6 and Figure 4.7 demonstrate the performance of our system that is calculated from expressions (4.3) and (4.4). As we focused on Figure 4.6, the average performance improvements we achieve with our systems compared to the best performance of the single design core only systems is about 14 % and we have only positive average improvement for all settings. The 14 % increase might not seem outstanding. We look for details about this 14 % increase. Figure 4.7 demonstrate the interesting results and problems of our static systems. The problem is also one of the problems of the genetic algorithm. Each individual PICTALL is ranged from about 120 % to 40 %. Most parts of settings in Figure 4.7 demonstrate the positive performance improvement or the same performance as the best performance for single design core only systems. As we describe, the magnitude of negative performance improvement or performance reduction is momentous because it reduces our average of APICTALL, even though the number of simulations which end up with negative result is about 20 % of the entire simulation results. Table 4.6 demonstrates the several data of our simulation. Table4.6 Statistical data of SPITCALL with BEST # of simulation % of Occurrence Average Total Number 4928 100 % 14.25 % Positive PITCALL 3919 79.53 % 22.33 % Zero PITCALL 69 1.40 % 0 % Negative PITCALL 940 19.07 % 18.39 % In the theory and our simulation setting, we should not get any result with a negative SPITC since all single core only configurations, which are GEN, LOG, MAT, FLP, and MEM, are one of the subsets in our search space. Therefore, if our optimization 57 method uses the exhaustive search, we could identify these configurations as a superior configuration whenever it is appropriate. The reason why we cannot find these configurations can be explained with the one of the weaknesses of a genetic algorithm. The genetic algorithm uses a stochastic search method. During the generation of the set of candidate chromosomes, we have a certain probability to generate each candidate based on a choice of parents. There are certain probabilities that we do not check a certain candidate. Therefore, there is always nonzero probability that we cannot find the truly optimized candidate. What we end up with in our optimization process is local optimums that are different from the global optimum. This result is well displayed when we refer to Figure 4.8 which shows the APITCALL with AVER and Figure 4.9 which shows SPITCALL with AVER. AVER, which is the average of the “best” values we find over the individual iteration, is much less than the BEST, which is the “best” we find over all iterations (Data for SPITCALL with AVER is displayed in Table 4.7). The reason is that there are some probabilities that the algorithm could not find the true “optimum” within the single iteration. Figure4.8 APITCALL with AVER for different types of system 58 Figure4.9 SPITCALL with AVER among systems Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. X Axis is for the sequence pattern of applications from P01 to P64 in Table B.1 and Table B.2; Table4.7 Statistical data of SPITCALL with AVER # of simulation % of Occurrence Average Total Number 4928 100 % 16.44 % Positive PITCALL 2220 45.05 % 11.90 % Zero PITCALL 1 0.02 % 0 % Negative PITCALL 2707 19.07 % 20.68 % We can easily improve our algorithm by introducing 5 single design core only systems into the first generation of our search. With this method, we are sure the search space of simulation includes the single design core only cases. Also this modification improves the search area of the algorithm since the single design core only systems are not similar to each other. As a result, our search algorithm can produce better results. Simulation results of the modified algorithm are displayed in Figure 4.10 through Figure 4.12. The APITCGEN and SPITCGEN with BEST are in Figure B.14 through Figure 59 B.21. Compared with Figure 4.10 through Figure 4.13, our algorithm shows improvement in the optimization abilities. We have only positive performance improvements in both SPITCALL with BEST and SPITCALL with AVER. The negative SPICTALL is replaced with the zero or the positive SPICTALL since we increase the variety of systems in the first generation and we are forced to evaluate the 5 different types of single core only systems. Figure4.10 APITCALL with BEST for different types of system with modified algorithm Figure4.11 SPITCALL with BEST among systems with modified algorithm Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. 60 Figure4.12 APITCALL with AVER for different types of system with modified algorithm Figure4.13 SPITCALL with AVER among systems with modified algorithm Each entry in the graph is a specific setting (S001 – S077) in Table B.3 through B.6. 61 Figure4.14 Changes on number of cores in APITCGEN for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. Figure4.15 Changes on number of cores in APITCGEN2 for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. 62 Figure 4.14 displays the APITCGEN for BEST. According to this figure, performance improvement compared to GEN which has the same number of cores as the comparison target, becomes the largest when we have 4 core systems, then our percentage of improvement keeps decreasing. Since the maximum amounts of total inforuction generated in a cycle are fixed, the utilization of the system compared to systems with general core only cannot be optimized if we have too many cores. The fixed amounts of inforuction generated per cycle, which is 64, come from the maximum processing power of an 8 core system. If we adjust the data to compare with the APITCGEN with 2 cores (GEN2), we observe a graph as Figure 4.15. The graph demonstrates the remarkable improvement when we increase the number of cores from 2 to 4. With this change, the maximum processing power of the system becomes half of the total amounts of infoructions generated per cycle. The result of this comparison clearly displays the diminishing performance improvement when we increase the number of cores in a system, especially if the system can only prefetch the fixed amounts of inforuction per cycle. When we increase the number of cores from 2 to 4, we efficiently reduce the cause of stalls and do not increase the probability of emptyrunning at the same time. After the 4 core system, chances of empty running are increased more than decrease in the chances of stalls. Therefore the performance is not improved as in the case of 4 cores. If we plot the same graph compared to the best single cores instead of GEN, the figure looks slightly different from the figures we observe. Figure 4.16 has similar characteristic as the previous figures up to 10 core system. However, we have the improvement for 12 and 14 cores systems. The reason why we cannot observe this 63 improvement in the previous two figures can be explained with Figure 4.11. For the comparison with the best of single design core only settings, we have more range of changes in the performance measurement for each individual setting and each individual inforuction pattern. Therefore, we observe the improvements for 12 and 14 cores. Figure4.16 Changes on number of cores in APITCALL for BEST Legend explains the rest settings of simulation with the following format: Cycles of each application: Stall trigger levels: Number of iterations. Figure4.17 Changes on APITCALL with different length of simulation for BEST Legend explains the rest settings of simulation with the following format: Number of cores: Stall trigger levels: Number of iterations. 64 Figure 4.17 displays the changes of APITCALL by changing the number of minimum length of each application. In Appendix B, we have larger size of these figures in Figure B.22 through Figure B.24. As we observe in the figures, our static system does not demonstrate any firm changes such as a monotonous decrease or increase when we change the cycles of each application. Instead of a monotonous increase or decrease, we observe the APITCALL stays in about .5 % of deviations. This comes from the differences for each length of simulation in the actual percentage of inforuction stream we simulate. Hence, we conclude this relationship as the following statement: the number of cycles for each application does not change the APITCALL significantly. Therefore our static operation seems to have steady performance improvement compared to the best configuration from single design core only system for any number of cycles. Figure4.18 Changes on APITCALL for BEST with different iteration Legend explains the rest settings of simulation with the following format: Number of cores: Cycles of each application: Stall trigger levels. 65 When we study the graph in Figure 4.18, we can still verify the local optimum issues of the genetic algorithm, since the 10 iteration data has slightly smaller APITCALL compared to 15 iteration data. Therefore we should keep the number of iterations to a relatively large number to obtain the global optimum or better performance. Figure4.19 Changes on APITCALL for BEST with different stall trigger Legend explains the rest settings of simulation with the following format: Number of cores: Cycles of each application: Number of iterations. With Figure 4.19, we cannot observe the relationship between APITCALL and the changes of amounts of inforuction that causes the stall, which corresponds to size of the inforuction buffer that is related to the hardware hazards. Some of results display the performance improvement when we have tighter stall trigger condition and the others display a decrease in the performance with the tighter constraint. The conclusion of this observation is that the change in condition of stall trigger definitely changes the APITCALL, but we cannot predict the effect in APITCALL due to the changes in the inforuction buffers from the current observations. The reason we cannot observe the 66 steady changes in the performance might comes from the following points: the inforuction buffers still have large enough size to avoid most stalls, the best configuration for single design core only systems already avoid the stalls as much as possible, the significant changes are averaged in the process of calculation of APITCALL, and/or the changes of best performance of single core only systems eliminate the proof of performance changes as in the observation of Figure 4.16. In this chapter, we introduce the static genetic reconfigurable system which demonstrates the ability to find the optimized configuration. Even though our algorithm still remains the several rooms of improvement, we obtained the positive APITC with general cores only system for all settings. With the modified algorithm, we demonstrate the better performance in the optimization to each individual application sequence. This result stands for the following statement: the genetic algorithm and our static system can change configurations of the system to obtain better performance in PITCs. We also have to emphasize the following fact: the optimization process needs prior information of the stochastic data of inforuction generation or application sequences. Without any information, our static system and the static genetic algorithm would not produce the superior results and end up with meaningless results for reconfiguration. 67 CHAPTER 5 DYNAMIC RECONFIGURABLE SYSTEM 5.0 Specific details of the dynamic genetic algorithm Since we discuss details of dynamic system in the previous sections, we will not repeat the same topic. Instead, we describe a topic which has not been discussed yet. That is how we determine the time to finish the previous reconfiguration process and start the new reconfiguration process. We have to use fixed time to estimate the fitness values, but we do not have to use the fixed time to terminate. We identify this time as reconfiguration time, which is the time we terminate the old reconfiguration process and then start the new process. If we do not choose this time interval carefully, our performance does not correspond to what we achieve in the real situation. For example, if we choose time interval shorter than the actual time for the reconfiguration of a FPGA (Field Programmable Gate Array) device, our simulation result is not realistic. Also, we have to take into consideration the calculation time for our reconfiguration process, since the timing of reconfiguration will change the performance we can get from our system. In addition to the fitness function we define in the former section, we add one more parameter that memorizes the changes of processing performance within a time 68 interval. After we find the best candidate by a genetic algorithm, we evaluate the predicted processing power of both the current configuration and the best candidate configuration. We compare these candidate performances for each time unit, beginning with the time frame we use for the genetic algorithm to the time of reconfiguration penalties. The time step we find through this process is set as the reconfiguration time that we previously defined. The flowchart of this process is shown in Figure 5.1, and the entire flowchart of the dynamic genetic algorithm is shown in Figure 5.2 and Figure 5.3. Figure5.1 Reconfiguration time determination process Start Set to the fixed time Decrement timer Check performance Satisfied Not Satisfied Stop NOT satisfied Check performance Satisfied 69 Figure5.2 Operation flowchart for the dynamic genetic algorithm Start Initialization Processing Stall? Not Happened Happened Stop Complete? Completed Not completed Flag? Genetic Algorithm Generation Better? Time? Off No Modification Yes Passed Not Passed On 70 5.1 Simulation settings In the previous chapter, we verify that the optimization ability of the genetic algorithm with the static reconfigurable system on the average. We use several fixed settings as common factors between the previous chapter and the present chapter, such as: stochastic information of inforuction generation in each application, number of different application, total number of inforuction generated in a given cycle, the number of core in a system, types of core architecture, types of inforuction, performance of each type of core architectures that are listed in Table 4.2, .Table 4.3 and Table 4.4. We change the number of generation to smaller number since we want to run this algorithm faster and the generation is the only stopping criteria as we describe. We also do not limit the size of the population inside the algorithm, but we limit the size of the population which carries over to the next implementation of the genetic algorithm. These fixed settings, Figure5.3 Brief Description of flowchart of the dynamic genetic algorithm 1.) Initialization Stage a. Set the number of application and number of iteration for each application 2.) Generation Stage a. Create the specific total amounts of information 3.) Reconfiguration Flag Check Stage a. Check whether reconfiguration is currently in the process or not 4.) Genetic algorithm Stage a. Implement genetic algorithm to find the better configuration 5.) Verification Stage a. Check whether the new configuration produce the better or not 6.) Process Stage a. Increment the time unit b. Process the # of information for the current processing power 7.) Stall Check a. Check whether the stall is happened or not 8.) Information check a. Check whether all information is completed or not 9.) Reconfiguration time Check a. Check whether the reconfiguration time is passed after the trigger of reconfiguration 10.) Modification Stage a. Change the performance of the system by adding the restriction or removing it 71 which are different from Table 4.4, are listed in Table 5.1. Also we use several variable settings as common to the setting listed in Table 4.5. The settings for variable parameter are listed in Table 5.2. All combinations of setting are listed in Table B.11 – Table B.14. As we describe in the previous chapter, we will observe the differences in the performance of static reconfigurable system and dynamic reconfigurable system. We could repeat the algorithm as we did in the static system, but we put more focus on the speed of the algorithm, since this is a timecritical operation which the environment changes as time goes and performance improvement is also dependent on the time we complete the algorithm. The fixed time we describe during the previous section is determined from the expression (5.1) Table5.1 Common setting for all simulation Setting # of total simulation 64 ( = 4^3) [same as Table 4.4] Total # of Inforuction at a time unit 64 [same as Table 4.4] Size of Initial population 15 [same as Table 4.4] # of generation 45 Maximum carry over factor (size) 4 (60 = 4*15) Dependencies factor .05 Prediction factor 2 Table5.2 Variable Setting for each simulation Candidates of setting we will setting # of cores in the system 2, 4, 6, 8, 10, 12, 14 [same as Table 4.4] Length of each application 50,100, 200, 400 Reconfiguration penalties 6,8,10 Stall trigger 30, 50 [same as Table 4.4] 72 5.1 where RP is reconfiguration penalties The choice of reconfiguration penalty is based on [34], where they said that the time necessary to complete the full programmable device is typically done in several microseconds and is dependent on the type of devices used for the reconfiguration. Also the time is dependent on the area that needs to be reconfigured [34]. In addition to the actual reconfiguration time, which is the time necessary to change the architecture, we need to think about the time to calculate the best dynamic architecture corresponding to the inforuction streams as we describe previously. The process of calculation can be implemented along with processing of inforuction in our main system. So we choose the reconfiguration penalties, which are sum of time necessary to change the architecture and time needs to calculate the optimized candidates, as 6, 8, and 10 cycles. We run the MATLAB codes with computers which have the same specifications as listed in Table 4.1. The cumulated numbers of computers used for dynamic system simulation is 102 since we simulate each individual setting with a different computer. 5.2 Simulation Results and Observations As we describe in the previous chapter and this chapter, we can use several results of observations from the previous chapter, since we use common settings. We set the model of the conventional system as general cores only and use the performance measurement of our system which is similar to what we derive in expression (4.1) and (4.2). We use the both SPITCGEN and APITCGEN, and also we use the SPITCBEST 73 and APITCBEST, in which BEST is the result of static systems in the previous chapter. The expressions to calculate SPITCBEST and APITCBEST are in expression (5.2) and (5.3). With these methods, we can easily compare the results of performance improvements from the different types of systems. 1 5.2 Σ 5.3 where BEST performance we obtain in Chapter 4 Figure5.4 SPITCBEST with dynamic systems Each entry in the graph is a specific setting (D001 – S077) in Table B.11 through B.14. Figure5.5 APITCBEST with dynamic systems 74 Figure5.6 SPITCGEN with dynamic systems Each entry in the graph is a specific setting (D001 – S102) in Table B.11 through B.14. Figure5.7 APITCGEN with dynamic systems Figure 5.4 and Figure 5.5 display the simulation results with SPITCBEST and APITCGEN. From these figures, we have to conclude that dynamic systems might not perform as well as the static systems, w 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


