Towards an energy-consumption based complexity classification for resource substitution strategies Hagen Höpfner Christian Bunse Bauhaus-University of Weimar University of Mannheim Bauhausstraße 11 A 5, 6, Gebäudeteil B, Seminargebäude 99423 Weimar, Germany 68131 Mannheim, Germany hoepfner@acm.org Christian.Bunse@informatik.uni- mannheim.de ABSTRACT vices in order to solve more complex tasks than it would be possible Protecting the environment by saving energy and thus reducing car- with a single device. Clouds are either used to store data or to dis- bon dioxide is one of today’s hottest topics and is of a rapidly grow- tribute workload. Thus, various hardware resources with different ing importance in the computing domain. In addition, to ecologi- properties are utilized for data processing and storage. One essen- cal reasons here issues such as the up-time of mobile or embedded tial difference between these resources is their energy consumption devices, battery charge cycles etc. are key problems. Recent stud- in relation to their performance. Large data centres already started ies have shown that software has a major impact onto the energy to optimize their ’Power Usage Effectiveness’ (PUE) that deter- consumption of the device it is executed on. Thus, intelligent se- mines the energy efficiency and that is determined by dividing the lection and assembly of software components promises significant amount of power entering a data centre by the power used to run savings. However, this requires knowledge about how much energy the computer infrastructure within it. For single devices this step is a (software) component consumes. In other words, a classification to be done in the near future. scheme following the idea of the European Union energy label is re- quired. This paper discusses recent findings and first ideas of estab- Especially for mobile devices that are typically battery-driven, en- lishing an energy classification scheme for software, using the ’big- ergy consumption has to be optimized/reduced since the amount of O’ notation as its general metaphor. The scheme is motivated, in- energy consumed is correlated to the up-time of the device. Recent troduced and validated by using resource substitution strategies, as research efforts have shown that such resources can be substituted one means for optimizing energy consumption via software adap- by each other to optimize one resource. Hence, it is possible to re- tation. We demonstrate that the classification scheme can be used design a software system in such a way that the available resources to characterize the fitness of a strategy and/or algorithm. Further- are used in an energy efficient manner. In other words, one re- more, we discuss to use such energy labels/classes when estimating source might be substituted by one or more other resources (e.g., the energy consumption of systems assembled from different com- exchanging memory consumption against processing power) in or- ponents. der to optimize the usage of the first resource. Unfortunately, there is no formal basis that classifies the ’fitness’ of a chosen substitu- 1. INTRODUCTION AND MOTIVATION tion strategy regarding energy efficiency. The basic idea of computing is that software utilizes hardware in order to solve well-defined problems and ease human life. This This paper presents first ideas towards an energy-consumption based started by supporting the task of calculating trajectories of missiles complexity-classification for resource-substitution-strategies. We and now covers nearly all aspects of human life. Almost all stan- therefore generalize our previous findings regarding the energy con- dard computers and even modern mobile devices like smart phones, sumption of basic algorithms (i.e., sorting and basic DB algorithms laptops, or embedded systems are based on the well known Von- such as joins) and the application of resource-substitution strate- Neumann-Architecture [19]. Data and program code is stored in gies. The goal is to define a formal classification scheme, similar to main memory. The central process unit (CPU), comprised of a con- the big-O Notation that can be used to classify the ’energy-fitness’ trol and arithmetic-logic unit, accesses the memory (i.e., a single of strategies and algorithms. By having such a classification it will separate storage structure) over a bus system. Nowadays it is com- be possible to not only characterize the performance and memory mon, that computers are connected to networks like the Internet. usage but also the energy consumption of a system. This enables information exchange and task distribution among de- vices with different in-built resources. Current trends in software The remainder of this paper is structured as follows: Section 2 in- development like .NET make use of this cloud of heterogeneous de- troduces the principle of resource substitution and covers related work. Section 3 focuses on energy consumption and closely inves- tigates the actual energy consumption of the considered resources. Section 4 discusses our ideas on the energy complexity classifica- tion. Finally, section 5 summarizes the paper and gives an outlook on future research. Copyright is held by the author/owner(s). GvD Workshop’10, 25.-28.05.2010, Bad Helmstedt, Germany. 2. RESOURCE SUBSTITUTION — STRA- CPU vs. Communication: A high CPU load can be substituted by TEGIES & TECHNIQUES data communication. CPU-intensive calculations might be In general, a resource is any physical or virtual entity of limited outsourced to a server [14] or distributed among many com- availability. Three main aspects can characterize resources: utility, puters [1]. For example, semantic caching is a CPU-intensive quantity, and use. This is especially true for mobile and embed- approach. [10] presents an approach for migrating the task ded systems that are characterized by a scarcity of resources. Such of finding reusable data in the cache to the server. In addi- systems typically depend on the resources that are provided by the tion, [11] analyzes server site cache invalidation. Although, device the system is executed on, or the environment infrastructure. both approaches require complex software operations on the In detail, the following resources are in the main focus: server, they drastically reduce client CPU load. On the other hand, we can easily reduce data transmission by using com- pression, which requires additional CPU usage. • The Central Processing Unit (CPU) is responsible for exe- CPU vs. Memory The substitution of CPU load by memory ac- cuting the instructions of a computer program. In principle cess is the well known as view materialization in the area of each CPU consists of an arithmetic logic unit (ALU), a con- database systems. In general this represents the decision re- trol unit, and registers (on-CPU-memory). There are various garding the storage of temporary results. In order to save CPUs available on the market, e.g. XScale, SnapDragon, CPU cycles one can also use alternative access paths (in- other processors based on the ARM architecture, Intel’s x86 dexes) to the data. Furthermore, standard compression ap- processors or the processors of the PPC family. proaches might be used for saving memory. • The memory of a computing system stores data and program Memory vs. Communication Replication and caching can reduce code. In general it can be divided into main memory (RAM), the amount of communication. However, full replication re- secondary memory (hard discs) and tertiary memory (DVD, duces communication, whereas the efficiency of caching de- tapes, etc.). Storing data on mobile devices differs from stor- pends on the re-usability of cached data [6]. The benefit of ing data on classic computers. Mobile devices typically use caching not only depends on the memory but also on the flash memory. Especially recent Smart-Phones or even some CPU. In general one it can be stated that data, available on a variants of Apple’s ’MacBook Air’ use this media as sec- device, must not be transmitted. But, redundant data might ondary memory. Nearly all current mobile devices allow the be outdated. Hence, synchronization mechanisms that con- use of additional storage media in form of memory cards or nect to a server or receive updates via a broadcast channel are Microdrives. required. The substitution of the resource memory by com- • While a bus system is responsible for in-computer commu- munication is common for data centres where data is stored nication, networks are used for inter-computer communica- at central places. If a client needs the data accesses the server tion. The overall principle is that the sender prepares and ad- and reads the data. There are certain approaches following dresses the data to send and transmits it electronically or opti- this substitution strategy (e.g., the Internet message access cally via wire or through the air (wirelessly). Today, a device protocol (IMAP) allows to read email without prior down- can have basically network access almost everywhere. Wire- load). less local-area networks are hot-spotted networks with a rea- sonable speed. GSM-networks (and extensions like GPRS, EDGE or HSDPA) are slower but widely available. UMTS- As discussed earlier, the idea of using resource substitution to opti- infrastructure has been installed all over Europe but full cov- mize the use of a specific resource stems from the domain of mIS. erage is far from existing. Here, especially the resource memory is oversimplified. It is com- mon to reduce the usage of secondary memory by caching data in primary memory. It is also common to swap data to secondary Different techniques for handling data in mobile information sys- memory if the primary memory does not have any space left. tems have different resource consumptions characteristics (CPU or memory focused, etc.). Interestingly, it is possible to exchange or 3. ENERGY CONSUMPTION REGARDING substitute resources by each other (i.e., resource substitution strate- gies) in order to optimize the use of one. Table 1 gives an general RESOURCES AND RESOURCE SUBSTI- overview about possible substitutions that holds for all distributed TUTION systems, and thus also for client/server information systems with In this paper we consider the following resources: CPU, primary mobile clients. According to this table, the resource communica- memory (RAM), secondary memory, network, whereby the latter tion might be replaced by the resources CPU or memory (e.g., do represents the communication aspects. As tertiary memory is mostly computations and store data locally). Unfortunately, Table 1 does used for backup purposes, we do not consider it in the addressed not include energy as a separate resource due to its orthogonal na- context of this paper regarding the use of resource substitution for ture being affected by other resources. However, due to ever in- reducing the energy consumption of a system. creasing functionality of mobile devices, limited battery capacities and environmental protection, energy consumption has to be ad- Energy consumption is usually correlated with hardware proper- dressed, too. ties. However, there are strategic issues and findings by other re- searchers that examine and argue about software properties that In the following we discuss in-depth the substitution possibilities have an impact on energy. Energy consumption associated with with respect to energy consumption. Even if these ideas originally wireless data-transmission is not negligible [7]. CPU usage needs were examined in the context of mobile information system (mIS) comparatively less energy than memory storage [16, 4]. Compress- [12], the findings can be generalized to all kinds of networked data ing a file by more then 10%, transmitting and decompressing it management applications. requires less energy than transmitting it uncompressed [18]. File substitute CPU Communication Memory CPU - Migration of computations Materialization and re-usage to the server of temporary results Communication Local execution of - Local data storage calculations Memory Data compression and Data management on - compact data structures the server only Table 1: Substitutable resources [3] compression also reduces the energy consumption of operations on Ec < Epr < Epw . hard disks [15]. Similar to primary memory, one can divide the energy consump- CPU based energy consumption Ec strongly depends on the used tion of secondary memory Es into Esr , Esw , and Ess . As a rule processor architecture (includes also the basic differences of RISC of thumbs one can estimate the energy consumption for reading or CISC based systems) and clock rate. For Intel desktop pro- data from a hard disk as n3LBA J. For one logical block this means cessors the energy consumption per instruction reaches from 10 · 1 Joule, for two blocks 8 Joule, etc. [13]. Interestingly sequen- 10−9 J for an i468 to 48 · 10−9 J for an Pentium 4 (Cedarmill) tial writing of huge amounts of data requires 4-5 times less en- processor [8]. Our own experiments based on the ATMega128L ergy than reading the same amount of data as the read/write heads processor and the measurement environment described in [4] re- movements are reduced. However, even if the real values differ sulted in 1.058 · 10−2 J for comparing two arrays of 1,000 integer extremely for different devices [20] one can extend the previous values stored in an SRAM module (128K, 12 ns). By normaliz- relation to Ec < Epr < Epw < Esr < Esw for single operations. ing this value after removing the energy required for reading both arrays, we calculated that 5.33 · 10−6 J are required for one com- Finally, we have to consider network communication. It’s energy parison on this processor. The energy consumption Ep of primary consumption can be divided into the energy required for sending memory operations can be divided into the energy that is required Ens and for receiving one Byte Enr . Especially wireless networks for reading Epr , for writing Epw and for keeping the state of this vary in their speed. Therefore, energy consumption for receiving a volatile memory Eps . As shown in [9] the following relation holds: certain amount of data also depends on the time for the “download”. Epr < Epw . The author calculated for one write access to SDRAM Regarding [2] receiving 50KB with a 20-second interval requires an energy consumption of 3 · 10−17 J whereas one read access con- 12.5J (UMTS), 5.0J (GSM), and 7.6J (WiFi). We have to note, sumed 1.811 · 10−17 J. The results of our experiments with the that these values are pure transmission values. Sending data re- ATMega128L processor are shown in Figure 1. Obviously, there quires more energy. The authors of [17] calculated idle:receive:send is also a difference between accessing the on-chip memory and the ratios as 1:1.05:1.4. Obviously, more energy (from CPU and main external SRAM module. memory) is required if packaging and addressing is taken into ac- count. To summarize this, we get the following relation for energy consumption of the resources involved in resource substitution: 0.00035 blind write to on-chip memory read from on-chip memory blind write to addition SDRAM 0.0003 Ec < Epr < Epw < Esr < Esw < Enr < Ens | {z } | {z } | {z } 0.00025 Ep Es En Energy consumption in Joule 0.0002 CPU usage requires less energy than using primary and secondary 0.00015 memory, and network communication requires even more energy. The goal of this paper is to quantify the energy consumption of 0.0001 strategies and algorithms in distributed environments. One can specify the overall energy consumption of such an algorithm or 5e-05 strategy as the sum E = Ec + Ep + Es + En . 0 50 100 150 200 250 300 350 400 450 500 550 600 650 700 750 800 850 900 950 1000 data size 4. ENERGY COMPLEXITY CLASSIFICA- TION In general, a complexity class is a set of problems of related resource- based complexity and is defined by the set of problems that can be Figure 1: Reading and writing data from and to memory solved by an abstract machine M using O(f (n)) of resource R, where n is the size of the input. In the context of this paper we Since the energy (consumption) is a function over time, it does are interested in the usage of resources. This is typically covered not make sense to take Eps into account while thinking about re- by the big-O notation that describes the limiting behaviour of a source substitution. Furthermore, we have to consider the CPU function. It allows to simplify functions in order to concentrate instructions required for reading and writing memory cells as well on growth rates. Thus, big-O can be used to describe an algo- as the energy consumptions required for transferring data between rithm’s usage of computational resources (e.g., the worst case or CPU and memory. Therefore, we can extend the first relation to average case running time or memory usage of an algorithm is of- ten expressed as a function of the length of its input). This allows 5.33 · 10−6 · (n · log(n)) + fp (n). To simplify the task for algorithm designers to predict the behaviour of algorithms and to the model fitter we first calculated E(n) − 5.33 · 10−6 · (n · choose the best fitting algorithm (regarding its complexity class), log(n)) = fp (n), copied the data to Eureqa, and searched in a way that is (nearly) independent of the computer architecture for fp (n). The tool found various functions, e.g. 1.02553 · or clock rate. Regarding the definition of complexity class for en- 10−5 · n − 5.1406 · 10−5 · log(0.0033665 · n − 0.0236113) − ergy we have to consider the resources involved in the computation. 0.000269206. Almost all of them have shown an n − log(n) Therefore, we have to distinguish and explicitly separate four sub- structure. As we know that each comparison requires read- components: Oc (fc (n)) is the complexity for the CPU which is ing the comparison partners from memory, the memory ac- equivalent to the well known running time, since the energy con- cess complexity of our Mergesort implementation is O(n · sumption of a CPU is related to the number of instructions which, log(n) + n − log(n)), which equals O((n − 1) · log(n) + n). in turn depends on the size of the input. Similarly one can say that the complexity Op (fp (n)) corresponds to memory-usage complex- ity, since the energy consumption of primary memory depends on For analyzing the secondary storage complexity and the network the number of read/write operations, which are derived or based on complexity one could use monitoring tools for file systems and the input size. We have to point out that memory-usage complexity network traffic in combination with model fitting techniques. How- is not equivalent to the memory complexity known from theoretical ever, we did no experiments in this regard so far. computer science. The memory complexity describes the required amount of memory but does not include the memory accesses. Ob- 5. SUMMARY, CONCLUSIONS, AND OUT- viously, an algorithm could use only a constant amount of mem- LOOK ory but read/write it several times. The same holds for the com- Energy consumption is becoming a central issue for most user and plexity Os (fs (n)) class characterizing the energy consumption of manufacturers of computing devices and especially of mobile or secondary memory. As the number of data transmissions is a func- embedded systems. Reasons are manifold and range from pro- tion over the input size, too, On (fn (n)) might express the energy tecting the environment to extending the up- and operating-time complexity for the network resource. We learned from the pre- of a system. However, the development and use of such, energy vious chapter that energy consumptions of resources vary. Hence, aware, systems, requires clear indication on the energy it consumes we have to use the energy characteristics of the resources as scaling and, for the sake of easy comparison and selection, the distinc- factors. For simplification we assume that Ec is the energy required tion of energy classes. This becomes even more important, when for processing one input element, Ep and Es for storing and retriev- it comes to software, since software has a major impact onto the ing one input element to/from main memory or secondary storage, energy consumed by a system. Within this paper we presented our respectively, and En for sending/receiving one input element via ideas regarding the definition of such software classification ap- the network. Therefore, the energy complexity of an algorithms is proach that uses the ’classic’ big-O notation as its metaphor. As given as sum: a starting point we concentrated on resource substitution strate- OE (fe (n)) = Oc (Ec · fc (n)) + Op (Ep · fp (n)) + Os (Es · fs (n)) gies/algorithms since those have shown their potential in making a system energy-aware [3]. We introduced different strategies and +On (En · fn (n)) discussed their energy-consumption related characteristics. Based on that we introduced and applied a classification scheme for en- ergy consumption. The scheme provides valuable information about the fitness of specific algorithms and strategies regarding the opti- Finding the energy complexity (sub)functions. As men- mization of energy consumption of a system. However, these ideas tioned earlier, the overall energy complexity class can be notated as have to be applied in practice (e.g., defining the energy class of dif- the sum of the class functions of the involved resource. Obviously, ferent algorithms, etc.). The next step then is to come up with tech- it is possible to analyze the program code in order to find the re- niques for determining the energy class of assembled components spective (sub)functions. However, the running time complexity for and or systems. Furthermore, we plan to define techniques and most algorithms is known. Considering only CPU and RAM usage tools for the development of energy-aware software systems that one can find the memory-access complexity by analyzing energy make use of energy classes. Finally, we are currently discussing a measurements. We described the measurement approach used in realistic case study to demonstrate the feasibility and applicability the following in [4]. Hence, Ec ·fc (n) is the function of the runtime of our ideas in practice. complexity multiplied with the energy required for one operation. For example, for Mergesort fc (n) = n · log(n) holds. We mea- 6. REFERENCES sured the energy for one operation Ec (in this case for one value [1] D. P. Anderson, E. Korpela, and R. Walton. comparison) as well as the energy E(n) required by the algorithm High-Performance Task Distribution for Volunteer for various n. We know, that E(n) = Ec · fc (n) + Ep · fp (n) Computing. In Proceedings of the First International holds. Hence, we can use model fitting techniques and tools like Conference on e-Science and Grid Computing, pages Eureqa1 for finding fp (n). 196–203, Washington, DC, USA, 2005. IEEE Computer Society. available online: http://citeseerx.ist. psu.edu/viewdoc/download?doi=10.1.1.84. Example: Given the running time complexity O(n · log(n)) of 840&rep=rep1&type=pdf. Mergesort, the energy of 5.33 · 10−6 J consumed for one [2] N. Balasubramanian, A. Balasubramanian, and comparison and the normalized overall energy E(n) (E(10) = A. Venkataramani. Energy consumption in mobile phones: a 0.00006042J . . . E(1000) = 0.0100312J consumed by ex- measurement study and implications for network ecuting the algorithm for various n [5], we can find the memory- applications. In Proceedings of the 9th ACM SIGCOMM access complexity fp (n) by using the target function E(n) = conference on Internet measurement conference, pages 1 http://ccsl.mae.cornell.edu/eureqa 280–293, New York, NY, USA, Nov. 2009. ACM. available online: http://www.cs.umass.edu/~arunab/ INFORMATIK 2004, Band 1, volume P-50 of Lecture Notes paper/tailender-imc09.pdf. in Informatics (LNI), pages 298–302, Bonn, Germany, Sept. [3] E. Buchmann. Konzeption und Implementierung eines 2004. GI, Köllen Druck+Verlag GmbH. in German, available Speichermanagers für ein konfigurierbares, leichtgewichtiges online: http://cs.zblmath.fiz-karlsruhe.de/ DBMS. Diplomarbeit, FIN, Otto-von-Guericke Universität LNI/Proceedings/Proceedings50/ Magdeburg, Magdeburg, Germany, Feb. 2002. in German, GI-Proceedings.50-64.pdf. supervised by Hagen Höpfner. [11] H. Höpfner. Update Relevance under the Multiset Semantics [4] C. Bunse, H. Höpfner, E. Mansour, and S. Roychoudhury. of RDBMS. In T. Kirste, B. König-Ries, K. Pousttchi, and Exploring the Energy Consumption of Data Sorting K. Turowski, editors, Mobile Informationssysteme, volume Algorithms in Embedded and Mobile Environments. In P-76 of LNI, pages 33–44, Bonn, Germany, 2006. GI, Köllen Proceedings of the 10th International Conference on Mobile Druck+Verlag GmbH. available online: Data Management: Systems, Services and Middleware http://subs.emis.de/LNI/Proceedings/ (MDM 2009), 18-20 May 2009 Taipei, Taiwan, pages Proceedings76/GI-Proceedings-76-3.pdf. 600–607, Los Alamitos, CA, USA, 2009. IEEE Computer [12] H. Höpfner and C. Bunse. Ressource Substitution for the Society. ISBN: 978-0-7695-3650-7, Realization of Mobile Information Systems. In J. Filipe, http://doi.ieeecomputersociety.org/10. M. Helfert, and B. Shishkov, editors, Proceedings of the 2nd 1109/MDM.2009.103. International Conference on Software and Data Technologie [5] C. Bunse, H. Höpfner, S. Roychoudhury, and E. Mansour. (ICSOFT 2007), July 22-25, 2007, Barcelona, Spain, volume Choosing the “best” Sorting Algorithm for Optimal Energy Software Engineering, pages 283–289, Setúbal, Portugal, Consumption. In B. Shishkov, J. Cordeiro, and A. K. July 2007. INSTICC, INSTICC press. available online: Ranchordas, editors, Proceedings of the 4th International http://www.hoepfner.ws/images/papers/ Conference on Software and Data Technologie (ICSOFT icsoft07.pdf. 2009), July 26-29, 2009, Sofia, Bulgaria, volume 2, pages [13] A. Hylick, R. Sohan, A. Rice, and B. Jones. An Analysis of 199–206, Setúbal, Portugal, July 2009. INSTICC, INSTICC Hard Drive Energy Consumption. In E. L. Miller and C. L. press. ISBN: 978-989-674-010-8, available online: Williamson, editors, Proceedings of the 16th International http://www.hoepfner.ws/images/papers/ Symposium on Modeling, Analysis, and Simulation of icsoft09.pdf. Computer and Telecommunication Systems (MASCOTS [6] A. Caracaş, I. Ion, M. Ion, and H. Höpfner. Towards 2008), pages 103–112, Los Alamitos, CA, USA, Sept. 2008. Java-based Data Caching for Mobile Information System IEEE Computer Society. available online: Clients. In B. König-Ries, F. Lehner, R. Malaka, and http://www.cl.cam.ac.uk/~acr31/pubs/ C. Türker, editors, Proceedings of the 2nd conference of hylick-harddrive2.pdf. GI-Fachgruppe MMS, volume P-104 of LNI, pages 97–101, [14] I. Ion, A. Caracaş, and H. Höpfner. MTrainSchedule: Bonn, Germany, 2007. GI, Köllen Druck+Verlag GmbH. Combining Web Services and Data Caching on Mobile available online: Devices. Datenbank-Spektrum, 21:51–53, May 2007. http://subs.emis.de/LNI/Proceedings/ available online: http://www. Proceedings104/gi-proc-104-009.pdf. datenbank-spektrum.de/pdf/dbs-21-51.pdf. [7] L. M. Feeney and M. Nilsson. Investigating the energy [15] A. Kansal and F. Zhao. Fine-grained energy profiling for consumption of a wireless network interface in an ad hoc power-aware application design. ACM SIGMETRICS networking environment. In Proceedings IEEE INFOCOM Performance Evaluation Review, 36(2):26–31, Sept. 2008. 2001, The Conference on Computer Communications, available online: Twentieth Annual Joint Conference of the IEEE Computer http://research.microsoft.com/~zhao/ and Communications Societies, Twenty years into the pubs/hotmetrics08joulemeter.pdf. communications odyssey, 22-26 April 2001, Anchorage, [16] P. Marwedel. Embedded System Design. Springer, 2007. Alaska, USA, volume 3, pages 1548–1557, Los Alamitos, [17] M. Stemm and R. H. Katz. Measuring and Reducing Energy CA, USA, 2001. IEEE. available online: http: Consumption of Network Interfaces in Hand-Held Devices. //www.sics.se/~lmfeeney/publications/ IEICE Transactions on Communications, Files/infocom01investigating.pdf. E80-B(8):1125–1131, July 1997. [8] E. Grochowski and M. Annavaram. Energy per instruction [18] J. Veijalainen, E. Ojanen, M. A. Haq, V.-P. Vahteala, and trends in intel®microprocessors. Technical report, M. Matsumoto. Energy Consumption Tradeoffs for Microarchitecture Research Lab, Intel Corporation, Santa Compressed Wireless Data at a Mobile Terminal. IEICE Clara, CA, USA, Mar. 2006. available online: Transactions on Communications, E87-B(5):1123–1130, http://support.intel.co.jp/pressroom/ May 2004. kits/core2duo/pdf/epi-trends-final2.pdf. [19] J. von Neumann. First Draft of a Report on the EDVAC. [9] T. Hirth. Energiecharakterisierung rekonfigurierbarer IEEE Annals of the History of Computing, 15(4):27–75, Oct. Rechensysteme. Diplomarbeit, 1993. http://dx.doi.org/10.1109/85.238389. Friedrich-Alexander-Universität Erlangen-Nürnberg, Institut [20] J. Zedlewski, S. Sobti, N. Garg, F. Zheng, A. Krishnamurthy, für Informatik, 2006. in German. available online: and R. Wang. Modeling Hard-Disk Power Consumption. In http://www4.informatik.uni-erlangen.de/ Proceedings of the 2nd USENIX Conference on File and DA/pdf/DA-I4-2006-06-Hirth.pdf. Storage Technologies, pages 217–230, Berkeley, CA, USA, [10] H. Höpfner. Serverseitige Auswertung von Indexen 2003. USENIX Association. available online: semantischer, clientseitiger Caches in mobilen http://www.cs.princeton.edu/~rywang/ Informationssystemen. In P. Dadam and M. Reichert, editors, papers/fast03/dempsey.pdf.