Abstract We are currently experiencing an explosive increase in the use of handheld mobile devices, such as cell phones, personal digital assistants (PDAs), digital camera's, global positioning systems, and so forth. Advances in technology enable portable computers to be equipped with wireless interfaces, allowing networked communication even while on the move. ubiquitous computing [16] ) will play a significant role in driving technology in the next decade. In this paradigm, the basic personal computing and communication device will be an integrated, batteryoperated device, small enough to carry along all the time. This device will be used as a replacement of many items the modern human-being carries around. It will incorporate various functions like a pager, cellular phone, laptop computer, diary, digital camera, video game, calculator and remote control. An i mportant issue will be the user interface: the interaction with its owner. To enable this, the device will support multimedia tasks like speech recognition, video and audio. Whereas today's notebook computers and personal digital assistants (PDAs) are self contained, tomorrow's networked mobile computers are part of a greater computing infrastructure. Furthermore, consumers of these devices are demanding ever-more sophisticated features, which in turn require tremendous amounts of additional resources. The technological challenges to establishing this paradigm of personal mobile computing are nontrivial. In particular, these devices have limited battery resources, must handle diverse data types, and must operate in environments that are insecure, unplanned, and show different characteristics over time [6] . Traditionally, (embedded) systems that have demanding applications -those driven by portability, performance, or cost -require the development of one or more custom processors or application-specific integrated circuits (ASICs) to meet the design objectives. However, the development of ASICs is expensive in time, manpower and money. In a world now running on 'Internet time', where product life cycles are down to months, and personalization trends are fragmenting markets, this inertia is no longer tolerable. Existing design methodologies and Another way to solve the problems has been to use general purpose processors, i.e. trying to solve all kind of applications running a very high speed processor. A major drawback of using these general-purpose devices is that they are extremely inefficient in terms of utilising their resources. To match the required computation with the architecture, we apply in the CHAMELEON project an alternative approach in order to meet the requirements of future low-power hand-held systems. We propose a heterogeneous reconfiguration architecture in combination with a QoS driven operating system, in which the granularity of reconfiguration is chosen in accordance to the model of the task to be performed. In the CHAMELEON project [15] we apply reconfiguration at multiple levels of granularity. The main philosophy used is that operations on data should be done at the place where it is most energy efficient and where it minimises the required communication. Partitioning is an important architectural decision, which dictates where applications can run, where data can be stored, the complexity of the mobile and the cost of communication services. Our approach is based on a dynamic (i.e. at run-time) matching of the architecture and the application. Partitioning an application between various hardware platforms is generally known as hardware/software co-design. In our approach we investigate whether it is possible and useful to make this partitioning at run-time, adapting to the current environment of the mobile device. Today, the choice of mobile devices is largely limited to simple wireless phones on the one hand, to complex and bulky laptops with wireless communication capability on the other. While these devices serve their purposes, they are neither the most integrated nor the most general: their functionality is often limited, they can operate for just a short time, and they are incapable of fully exploiting the emerging integrated wireless networks. Even while current devices have the ability to communicate and process data, they are and by large primarily either data processing devices or communication devices. Simply shrinking the processing devices and communication devices, and packaging them together does not alleviate the architectural bottlenecks of integrated mobile multimedia devices [12] . The real challenge is to design a device where d ata processing and communication share equal importance. Multimedia functionality is a driving force for many research challenges. For example, due to the size constraints on a portable computer, the user interface must be small. The shortage of area on a mobile device can cause us to trade buttons in favour of recognising the user's intention from analogue input devices such as handwriting, gesture and voice. Speech generation and recognition seem an ideal user interface since they require no surface area and allow hands-free and eyefree operation. However, general-purpose speech input and output places substantial storage and processing demands on a mobile device. Other research investigates the use of head-mounted virtual reality displays. The trend in mobile system architectures has been to shrink a general-purpose desktop PC into a package that can be conveniently carried. Even PDAs have not ventured far from the general-purpose model, neither architectural nor in terms of usage model. Both the notebook and the personal computer generally use the same standard PC operating system such as Windows (CE) or Unix, same applications, use the same communication protocols and use the same hardware architecture. The only difference is that portable computers are smaller, have a battery, a wireless interface, and often use low power components. Even though battery technology is improving continuously and processors and displays are rapidly improving in terms of power consumption; battery life and battery weight are issues that will have a marked influence on how hand-held computers can be used. Energy consumption is becoming the limiting factor in the amount of functionality that can be placed in these devices. More extensive and continuous use of network services will only aggravate this problem since communication consumes relatively much energy. Another key challenge of mobile computing is that many attributes of the environment vary dynamically. Mobile devices face many different types of variability in their environment. Therefore, they need to be able to operate in environments that can change drastically in short term as well as long term in available resources and available services. Merely algorithmic adaptations are not sufficient, but rather an entirely new set of protocols and/or algorithms may be required. For example, mobile users may encounter a completely different wireless communication infrastructure when walking from their office to the 0-7695-0990-8/01/$10.00 (C) 2001 IEEE street. A possible solution is to have a mobile device with a reconfigurable architecture so that it can adapt its operation to the current environment and operating condition. Adaptability and programmability should be major requirements in the design of the architecture of a mobile computer. We are entering an era in which each microchip will have billions of transistors. One way to use this opportunity would be to continue advancing our chip architectures and technologies as just more of the same: building microprocessors that are simply more complicated versions of the kind built today. However, simply shrinking the data processing terminal and radio modem, attaching them via a bus, and packaging them together does not alleviate the architectural bottlenecks. The real design challenge is to engineer an integrated mobile system where data processing and communication share equal importance and are designed with each other in mind. Just integrating current PC or PDA architecture with a communication subsystem, is not the solution. One of the main drawbacks of merely packaging the two is that the energy-inefficient general-purpose CPU, with its heavyweight operating system and shared bus, becomes not only the centre of control, but also the centre of data flow in the system and a main cause of energy consumption. Another drawback is that highly optimised ASICs are inflexible, have a relatively long development time, and can only be applied optimally in a limited range of applications. Clearly, there is a need to revise the system architecture of a portable computer if we want to have a machine that can be used conveniently in a wireless environment. A system level integration of the mobile's architecture, operating system, and applications is required. The system should provide a solution with a proper energy-efficient balance between flexibility and efficiency through the use of a hybrid mix of general-purpose and the applicationspecific approaches [6] . A system wide approach that covers the whole spectrum between physical layer and applications c an provide significant energy savings [6]. A key challenge of mobile computing is that many attributes of the environment vary dynamically. Mobile devices operate in a dynamically changing environment and must be able to adapt to the new environment. For example, a mobile computer will have to deal with unpredicted network outage or should be able to switch to a different network, without changing the application. It should therefore have the flexibility to handle a variety of multimedia services and standards (like different video decompression schemes and security mechanisms) and the adaptability to accommodate the nomadic environment, required level of security, and available resources. Mobile devices need to be able to operate in environments that can change drastically in short term as well as long term in available resources and available services. Some short-term variations can be handled by adaptive communication protocols that vary their parameters according to the current condition. Other, more long-term variations generally require a much larger degree of adaptation. They might require another air interface, other network protocols, and so forth. A software radio that allows flexible and programmable transceiver operations is expected to be a key technology for wireless communication. Reconfigurable systems have the potential to operate efficiently in these dynamic environments. Reconfigurability also has another more economic motivation: it will be important to have a fast track from sparkling ideas to the final design. If the design process takes too long, the return on investment will be less. It would further be desirable for a wireless terminal to have architectural reconfigurability such that downloading new functions from network servers may modify its capabilities. Such reconfigurability would also help in field upgrading as new communication protocols or standards are deployed, and in implementing bug fixes [12] . Summarising, the key issues in the design of portable multimedia systems is to find a good balance between flexibility and high-processing power on one side, and area and energy-efficiency of the implementation on the other side. The spectrum of solutions 2.1. In general there is a whole range of possible solutions for a certain problem. In a direct hardware implementation, problems are solved by mapping an algorithm directly into hardware. That is, the resulting hardware reflects the solution directly. We call this fixed resources and fixed algorithms. With a processor we have a way to implement almost any algorithm using a fixed set of resources. The processor provides fixed resources in the form of ALUs, floating-point units, etc. The processor solves problems by providing 0-7695-0990-8/01/$10.00 (C) 2001 IEEE limited, fixed hardware resources and by sharing those resources over time. In addition, the same hardware can support multiple problems. The processor solution is one with fixed resources and dynamic algorithms. These two problem-solving mechanisms have been competing with each other. There is a trade-off between the flexibility of the processor and the efficiency of the direct hardware implementation. If the application requires the ultimate in performance and efficiency, a direct hardware solution is preferred. But if the problem is too expensive to solve with a direct hardware approach, a processor-based solution is indicated. Between these two extremes there is a large world of dynamic logic. With dynamic logic the engineer can select both the resources and the algorithm. Both the resources and the algorithms may vary over time to solve the problem. Dynamic resources and dynamic algorithms. Dynamic logic can be efficient because the appropriate resources for the problem can be chosen to exactly match the algorithm at any point in time. Figure 1 shows three different approaches in the spectrum of applications and hardware implementations, and illustrates the trade-off between efficiency and flexibility. Approaches A trend in computer architecture is to focus on flexibility with high performance general-purpose processors as this is the area in which a semiconductor vendor can enhance its status. Therefore, the architecture of a general-purpose processor is most widely studied, and optimisations for processor performance are the main goal. In general-purpose processors it is possible to map a large set of applications on the hardware simply by writing the right software for it. While general-purpose processors and conventional system architectures can be programmed to perform virtually any computational task, they have to pay for this flexibility with a high energy consumption and significant overhead of fetching, decoding and executing a stream of instructions on complex generalpurpose data paths. The energy overhead in making the architecture programmable most often dominates the energy dissipation of the intended computation [11] . The goal of application specific modules is to optimise the overall cost-performance of the system, and not performance alone. Application specific solutions present the most effective way of reducing energy consumption and have shown to lead to huge power savings. Performing complex multimedia-data processing functions in dedicated hardware that is optimised for energy-efficient operation reduces the energy-per-operation by several orders of magnitude relative to software. However, the disadvantage of dedicated hardware is the lack of flexibility and programmability, their functionality is restricted to the capabilities of the hardware. The technological challenges in the design of custom ASICs are usually significantly smaller than the design of general-purpose circuits. This means that high-performance custom chips can be designed and  From the discussion above, it is apparent that neither general-purpose processors, nor ASICs will be capable of satisfying the power and efficiency requirements of the future mobile devices. A hybrid solution with application domain specific modules could offer enough flexibility to be able to implement a predefined set of (usually) similar applications, while keeping the costs in terms of area, energy consumption and design time to an acceptable low level [1] . The modules are optimised for one specific application domain. A system designer can use the generalpurpose processor for portions of algorithms for which it is well suited, and craft an application domain specific module for other tasks. Unused parts of the system must be switched off when not needed. Summarising, an ASIC solution is too rigid, and a processor solution is too inefficient. In fact, we want to make the machine fit the algorithm as opposed to making the algorithm fit the machine. This is the area of reconfigurable computing systems. Reconfigurable computing systems combine programmable hardware with programmable processors to capitalise on the strengths of hardware and software. The earliest configurable computing machine was proposed, designed, and implemented by Professor Gerald Estrin at UCLA in the early 1960s [4] . Estrin proposed the "Fixed plus variable structure computer", where some fixed hardware was dedicated to an inflexible abstraction of a programmable processor and a flexible component implemented digital logic. Today, the most common devices used for reconfigurable computing are Field Programmable Gate Arrays (FPGA). FPGAs present the abstraction of gate arrays, allowing developers to manipulate flipflops, small amounts of memory, and logic gates.  In personal mobile devices, the system must meet the conflicting demands of compute intensive algorithms, communication intensive applications, and long battery life. In general, a designer tries to design a system to be optimal for a certain application and environment. The designer has to select a particular algorithm, design or select an existing architecture that can be used for it, and determine various parameters such as supply voltage and clock frequency. However, energy efficiency in mobile systems is not only a onetime design problem that needs to be solved during the design phase. In a mobile system, power management extents the notion of hardware/software co-design, since we have to face a highly dynamic application and communication environment. This multidimensional design space offers a large range of possible trade-offs. Adaptability and flexibility are two recurring items when we mention energy efficiency and performance on mobile multimedia computers. This leads to a key problem of energy policy optimisation, which must be the central issue in any energy management system. The policy is the algorithm that decides what measures have to be taken to minimise the energy consumption. Traditional power management schemes only decide how and when to activate or shut down system resources to minimise the energy consumption, depending on usage patterns and performance constraints. In the traditional design approach the designer needs to select one of alternative solutions, either hardware or software, for all parts of the system in the early phases of the design. However, in mobile systems energy efficiency is not only a one-time problem that needs to be solved during the design phase. When the system is operational, frequent adaptations to the system are required to obtain an energy efficient system that can fulfil the QoS requirements imposed. Finding the energy management policy that minimises energy consumption without compromising performance beyond acceptable levels is already a c omplex problem. If the resources are also flexible, and can adapt their functionality, this problem becomes even bigger. Mobile system functionality and partitioning In a reconfigurable mobile system functions can be dynamically migrated between functional modules such that an efficient configuration is obtained. Functionality can be partitioned inside a mobile system between a program running on the generalpurpose CPU, dedicated hardware components (like a compressor or error correction device), and field programmable hardware devices (like FPGAs). The networked operation of a mobile system opens up additional opportunities for decomposition to increase energy efficiency. One opportunity is offloading computation dynamically from the mobile system, where saving battery energy is at a premium, to remote energy-rich servers in the wired backbone of the network. In essence, energy spent in communication is traded for computation. For example, when we consider the transmission of an image over a wireless network, there is a trade-off between image compression, error control, communication, and energy consumption. Partitioning of functions is an important architectural decision, which indicates where applications can run, where data can be stored, the complexity of the terminal, and the cost of the communication service. The key implication for this architecture is that the run-time hardware and software environment on the mobile computer and in the network should be able to support such adaptability, and provide application developers with appropriate interfaces to control it. Software technologies such as proxies and mobile agents, and hardware technologies such as adaptive and reconfigurable computing are likely to be the key enablers. For multimedia applications in particular, a substantial reduction in energy consumption is possible as the computational complexity is high and their computation is regular and spatially local. Also, the communication between modules is significant. Improving the energy efficiency by exploiting locality of reference and using efficient application-specific modules therefore has a substantial impact on a mobile system. The term reconfigurability has a strong association with programmability. Programmability originates 0-7695-0990-8/01/$10.00 (C) 2001 IEEE from the 'stored-program' concept used in the computer world. A program is typically a set of instructions that modify dynamically the behaviour of statically connected modules such as memories, registers and datapaths. This has gradually been extended to include the dynamic reconfiguration of interconnect networks and logic functionality as well. Nowadays, reconfigurable systems are often constructed from (arrays of) field-programmable devices (FPGAs). These can give orders of magnitude in performance improvement for specific computational kernels over traditional computers by providing programmability (reconfigurability) at the gate level. However, this may come at the price of an increase in area, increase in energy consumption, and lower programming ease. It is arguable whether one should refer to the dynamic loading of a hardware configuration as programming or reconfiguration. The difference is indeed a bit subtle. Of course, even in dynamic logic there will be static hardware that will not change over time. Reconfiguration can be viewed as an extra layer of abstraction between programming and hardware. In programming, fixed instructions are used to solve a problem. The characteristics and meaning of these instructions is determined by the micro-program memory of the device. The 'instruction set' of the reconfigurable device is changed to meet the requirements of the algorithm. In some sense, there is a resemblance to dynamic micro-programming, in which the instruction set of the computer is changed by downloading microcode, rather than to run a single instruction set for all algorithms. Reconfigurability can actually be applied at many layers in a system, and at multiple levels of granularity, in which each has its own preferred and optimal application domain [13] . In the CHAMELEON project we use the term reconfigurability to denote all possible changes to solve a problem at various levels of the system architecture. So we extend the traditional notion of reconfiguration from being just the layer between programming and hardware, to actually a vertical parameter that involves many layers in the system. As said before, in a mobile multimedia system many trade-offs can be made concerning the required functionality of a certain mechanism, its actual implementation, and values of the required parameters. In an architecture with reconfigurable modules and data streams, functions can be dynamically migrated between functional modules such that an efficient configuration is obtained. For example, when we consider the transmission of an image over a wireless network, there is a trade-off between image compression, error control, communication, and energy consumption. Functionality can be partitioned between a program r unning on the general-purpose CPU, dedicated hardware components (like a compressor or error correction device), and field programmable hardware devices (like FPGAs). Of course, the actual trade-off will depend on the particularities of the system, the nature of the data sent, and so on. The main philosophy used is that operations on data should be done at the place where it is most energy efficient and where it minimises the required communication. This can be achieved by matching computational and architectural granularity. In the system we have a hierarchical granularity in which we differentiate multiple grain-sizes of operations. These levels are illustrated in Figure 2 , and will be discussed in more detail in Section 5. At the gate level, we have the already mentioned reconfigurable logic of which FPGAs are a typical example. Other options for reconfiguration are at the reconfigurable datapath, in which the modules have various functions like multiplication and addition (the Field Programmable Function Array (FPFA) that will be introduced in Section 5 is a typical example of this); at the reconfigurable dataflow in which streams of 0-7695-0990-8/01/$10.00 (C) 2001 IEEE data are dynamically configured between various application domain specific modules; and at a high level we can identify reconfiguration in the partitioning of the load between the mobile and an external server. To be able to handle this multi-level reconfigurability, a model is needed to describe the functionality and characteristics of the various processes, and also the interaction between them. The reconfigurable system we envision consists of a heterogeneous dynamically reconfigurable architecture that spans many levels of the system. To deal with the hierarchical granularity, a system model is used in which Quality of Service (QoS) and energy consumption play a crucial role. This model is used to dynamically partition tasks of an application such that an energy efficient configuration is established. An important issue of the research is to deal with the flexibility of the system. A trade-off has to be made where and when to run which (part of the) algorithm. Therefore, a high-level hierarchical -QoS based -model is needed to predict the behaviour of modules in terms of energy consumption, performance, cost etc., when running a certain set of applications. Besides describing the functionality of the modules and their ability to adapt (e.g. the effects on its energy consumption when the image compressor changes its frame rate, its resolution, or even its compression mechanism) this model also includes the interaction between these modules. Such a model is required to predict the overall consequences for the system when an application or functional module adapts its QoS, as in mobile systems, applications typically will have to adapt dynamically to the changing operating conditions. Using this model the inherent tradeoffs between for example performance, communication and energy consumption can be evaluated and a proper adaptation of the whole system can be made. Applications that users run on a mobile need several functional resources of the system, such as processor, memory, wireless network interface, and compression/decompression logic. In our architecture we assume that such modules are programmable and can adapt to the demands of the applications and to the state of the environment, e.g. available bandwidth, bit error rate, available energy, etc. In general these modules are not independent and choices for the setting of one module may influence other modules. For example: when video has to be transmitted it can be compressed, which reduces the required bandwidth on the wireless network. However, more compression requires not only more processing power, it also needs better error-control. All these functional modules often have contradictionary effects on the resources needed, and a trade-off has to be made to find an optimal solution. Not only the parameters can be changed as it might also be profitable to migrate complete function from one module to another, possibly even to another machine. A complicating factor is that the dynamic nature of a mobile environment also demands an architecture that allows adapting to quickly changing conditions. The hardware and software architecture should be able to support such adaptability and should minimise the energy consumption by determining in run-time, things like: • Algorithm -the most suitable algorithm(s) to execute the requested service(s). • Partitioning -an appropriate partitioning of the algorithms over the different heterogeneous parallel processing units, which may include base stations, CPUs, FPGAs and dedicated hardware. • Parameters -the most optimal parameters for execution of the algorithms. • Power state -the suitable energy status mode of the different hardware components. These decisions are related to each other and are strongly influenced by the environment, the current status of the system and the given constraints such as minimum required performance, real-time deadlines and minimum quality of service (QoS) parameters. For making these decisions a trade-off has to be made between computation, communication and initialisation costs (both time and energy) to adapt the status of the system dynamically to new circumstances in the best suitable manner. Multiple hierarchical levels will be used to hide complexity and achieve local adjustable systems when possible. A flexible communication mechanism is required to always offer the same communication interface independent of a specific processing unit, so allocation of algorithms to different processing units can be easily done. At all levels of abstraction, modern computing systems are built in terms of components and communication (or, at least, synchronisation) between components. Communicating systems imply 0-7695-0990-8/01/$10.00 (C) 2001 IEEE
Chameleon project REF considers a hybrid reconfigurable platform that contains microprocessor(s), an FPGA unit and coarse-grain reconfigurable units, called Field Programmable Function Arrays (FPFAs).
Energy management for dynamically reconfigurable heterogeneous mobile systems
Proceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 2001
Proceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 2001
Computer Science Physics