Wolfgang W. Osterhage Mathematical Theory of Advanced Computing Mathematical Theory of Advanced Computing Wolfgang W. Osterhage Mathematical Theory of Advanced Computing WolfgangW.Osterhage Wachtberg-Niederbachem,Germany ISBN978-3-662-60358-1 ISBN978-3-662-60359-8 (eBook) https://doi.org/10.1007/978-3-662-60359-8 #Springer-VerlagGmbHGermany,partofSpringerNature2020 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart ofthematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilarmethodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthors,andtheeditorsaresafetoassumethattheadviceandinformationinthis bookarebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernorthe authorsortheeditorsgiveawarranty,expressedorimplied,withrespecttothematerialcontained hereinorforanyerrorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwith regardtojurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. ThisSpringerViewegimprintispublishedbytheregisteredcompanySpringer-VerlagGmbH,DE, partofSpringerNature. Theregisteredcompanyaddressis:HeidelbergerPlatz3,14197Berlin,Germany Preface This book is the English translation of Wolfgang W. Osterhage’s Mathematische Algorithmen und Computer-Performance, Springer Vieweg, Heidelberg, 2016. It hasbeenenhancedbythefollowingitemsandsections: (cid:129) Chapter 5: Jump Transformations: Source code for computer art graphs and additionalmaterialinelectronicformof35realizationsofcomputerart (cid:129) Chapter6:DataManagement (cid:129) Chapter7:QuantumComputers. Initiallythisbookoriginatedfromacollectionofdisparatepapersallrelatedto computerperformance.Sinceacomprehensiveworkconcerningperformancehad alreadybeenpublished(s.References),thechallengewastosortofcompilealater supplement of these aspects and deliver it in an acceptable form. There are some special features in this book relating to two new algorithms and database theory, whichhavenotyetbeenputtothetestinthefield.Wehopetohavecalledforththe interestofsoftwareandhardwarearchitectsalike. Onthisoccasion,IwouldliketoexpressmyspecialthankstoMartinBörgerand SophiaLeonhardandtheirteamfortheirpatientsupportforthisproject. Wachtberg-Niederbachem,Germany WolfgangW.Osterhage v Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Terminology.. . . . . . .. . . . . . . .. . . . . . .. . . . . . . .. . . . . . 2 1.2 ThreeLevels. . .. . .. . .. . .. . .. . .. . .. . . .. . .. . .. . .. . . 2 2 PerformanceTheory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 SystemPerformance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 HardwareParameters. . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 CPU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.3 MainMemory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.4 Disks. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. . 24 2.1.5 I/O. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.6 OperatingSystemParameters. . . . . . . . . . . . . . . . . . . . 29 2.2 ApplicationPerformance. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.1 ApplicationParameters. . . . . . . . . . . . . . . . . . . . . . . . 30 Bibliography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3 Test-Automatisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2 WhyAutomatisation?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 ComparisonBetweenManualandAutomatedTesting. . . . . . . . 37 3.4 SymbolicExecution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.1 ChallengesandSolutions.. . . .. . .. . . .. . . .. . . .. . . 40 3.4.2 Tools. .. .. .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. . 41 3.5 Search-BasedAutomatedStructuralTesting. . . . . . . . . . . . . . . 42 3.5.1 GeneticAlgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2 Limits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.6 CombinationofSEandSBST. . . . . . . . . . . . . . . . . . . . . . . . 44 3.7 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Bibliography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 vii viii Contents 4 PreservationNumbers:ANewApproachinSoftComputing. . . . . 47 4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 CalculationsandObservations. . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 TheEconomyofCalculations. . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4 PreservationNumbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.5.1 Accuracy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.5.2 Efficiency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.6 Relationships. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.6.1 AccuracyandEfficiency. . . . . . . . . . . . . . . . . . . . . . . 52 4.6.2 Accuracy,EfficiencyandPreservationNumbers. .. . . . . 53 4.7 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.8 ChainsofCalculations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.9 Logic. .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 55 4.10 Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Appendix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5 JumpTransformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 JumpTransformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3 n-TupleTransformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.3.1 DefinitionsandRules. . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3.2 Characteristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.3.3 Formalizations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3.4 Examples. . .. . . .. . . .. . . .. . .. . . .. . . .. . . .. . . . 68 5.3.5 Inter-relationships. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4 RandomTriggerTransformations. . . . . . . . . . . . . . . . . . . . . . 72 5.4.1 DefinitionsandRules. . . . . . . . . . . . . . . . . . . . . . . . . 72 5.4.2 Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.5 Inter-transformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.5.1 Inter-relationshipsBetweenTwoRandomTriggers. . . . . 73 5.5.2 TransformationBetweenn-TupleandRandomTriggers.. . 75 5.6 Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.6.1 SetsandAddressSpaces. . . . . . . . . . . . . . . . . . . . . . . 75 5.6.2 Cryptography. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.6.3 ComputerArt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.6.4 Other.. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. . .. .. . 78 Appendix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Reference. .. . . .. . . . .. . . .. . . .. . . .. . . . .. . . .. . . .. . . .. . . . 86 Contents ix 6 DataManagement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.1 ArtificialNeuralNetworks. . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.1.2 TheModelforArtificialNeuralNetworks. . . . . . . . . . . 87 6.1.3 Applications. .. . .. .. . .. . .. . .. .. . .. . .. . .. .. . . 89 6.1.4 Reliability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.1.5 Multi-layerNeuralNetworks. . . . . . . . . . . . . . . . . . . . 90 6.2 DataManagementConcepts. . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.2.1 TechnicalConditions. . . . . . . . . . . . . . . . . . . . . . . . . 93 6.2.2 Accesses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.3 KnowledgeBasesandNeuronalTools. . .. . . . . . . . . . . . . . . . 97 6.3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.3.2 KnowledgeBasesandAI. . . . . . . . . . . . . . . . . . . . . . 97 6.3.3 AdvancedOptionsforDataBaseManagement. . . . . . . 98 6.3.4 Conclusion. .. .. ... .. .. .. ... .. .. .. ... .. .. .. . 101 7 QuantumComputers. . . .. . . . . . . . . . .. . . . . . . . . .. . . . . . . . . . 103 7.1 WhatIsIntelligence?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 7.2 QuantumComputers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.3 Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7.4 IntelligenceofQuantumSystems. . . . . . . . . . . . . . . . . . . . . . 107 Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 1 Introduction This book has to do with performance, but not as a general subject and not in completeness. It is about selected methods and how under certain conditions specificperformanceaspectscanbeimproved.Thismeansthat—contrarytoother publications (s. References at the end of the book)—for example considerations concerning process performance do not figure at all. The book is rather technical andpartlyspeculative. After anintroductory chapter, which deals with the basics of computer perfor- mance and provides a general overview, there are six chapters dedicated each to specific algorithms and techniques, which may play a role under a performance pointofview: (cid:129) SymbolicExecution(SE) (cid:129) Search-BasedAutomatedStructuralTesting(SBST) (cid:129) PreservationNumbersasanInstrumentofSoftComputing (cid:129) JumpTransformations (cid:129) DataManagement (cid:129) QuantumComputers. SEandSBSTareestablishedmethodsinautomatictestingofcomplexsoftware. Theyarerelevanttoensure andoptimize performanceduringextensivetests.The conceptofPreservationNumbersconstitutesanewapproachinsoftcomputingand could be used in complex mathematical applications, for example for numerical modeling or simulations in the technical-scientific area. Jump Transformations presentagainanewalgorithm,whichmayenabletogenerateoverlappingnumerical spaces on the basis of transformation boundaries, possible to be applied in the design of main memories to create competing address spaces within one and the samememoryforexample. #Springer-VerlagGmbHGermany,partofSpringerNature2020 1 W.W.Osterhage,MathematicalTheoryofAdvancedComputing, https://doi.org/10.1007/978-3-662-60359-8_1 2 1 Introduction InthechapteraboutDataManagementitisproposedtocombineadvanceddata managementtechniqueswithartificialneuralnetworktechnology. Finally the concept of quantum computers and first realization attempts are introduced against the backdrop of an intelligence definition culminating in the speculation,whetherquantumsystemsassuchcarryintelligenceatall. 1.1 Terminology The subject of performance optimization can be divided into three main parts of consideration: (cid:129) systemperformance (cid:129) applicationperformanceand (cid:129) processperformance. Allthreeareasaresubjectto: (cid:129) theory (cid:129) measurement (cid:129) analysisand (cid:129) optimization. 1.2 Three Levels Whentalkingaboutperformancepeopleusuallyrefertosystemperformanceonly— or to simplify it yet again: to the power of hardware, i.e. processor and main memory. This is the reason, why performance has been neglected during the last decades.Atsomestagehardwarebecamesocheapthatoptimizingbyprogramming techniques for example did not seem worthwhile, since manpower became more and more expensive. Hardware was bought and its extensions and as a result systems were running faster again. Or existing systems were configured so com- fortablythatperformanceproblemsjustdidnothappen. However,enduserexperiencespokeadifferentlanguage.Negativeperceptions ofresponsetimesdidnotonlyplayapsychologicalrolebutalsoaffectedthroughput indailybusiness.However,theratiobetweenhardwareinvestmentstooptimization