More Like this

1. Set it and forget it: utility-based scheduling for public displays

   https://doi.org/10.1007/s00779-020-01423-1  

   Bushman, Kristi; Labrinidis, Alexandros (June 2020, Personal and Ubiquitous Computing)

   null (Ed.)

   The pervasiveness of public displays is prompting an increased need for “fresh” content to be shown, that is highly engaging and useful to passerbys. As such, live or time-sensitive content is often shown in conjunction with “traditional” static content, which creates scheduling challenges. In this work, we propose a utility-based framework that can be used to represent the usefulness of a content item over time. We develop a novel scheduling algorithm for handling live and non-live content on public displays using our utility-based framework. We experimentally evaluate our proposed algorithm against a number of alternatives under a variety of workloads; the results show that our algorithm performs well on the proposed metrics. Additional experimental evaluation shows that our utility-based framework can handle changes in priorities and deadlines of content items, without requiring any involvement by the display owner beyond the initial setup. 

   more » « less
2. Efficient Deterministic Federated Scheduling for Parallel Real-Time Tasks

   https://doi.org/10.1109/RTCSA50079.2020.9203660  

   Dinh, Son; Gill, Christopher; Agrawal, Kunal (August 2020, 2020 IEEE 26th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA))

   null (Ed.)

   Federated scheduling is a generalization of partitioned scheduling for parallel tasks on multiprocessors, and has been shown to be a competitive scheduling approach. However, federated scheduling may waste resources due to its dedicated allocation of processors to parallel tasks. In this work we introduce a novel algorithm for scheduling parallel tasks that require more than one processor to meet their deadlines (i.e., heavy tasks). The proposed algorithm computes a deterministic schedule for each heavy task based on its internal graph structure. It efficiently exploits the processors allocated to each task and thus reduces the number of processors required by the task. Experimental evaluation shows that our new federated scheduling algorithm significantly outperforms other state-of-the-art federated-based scheduling approaches, including semi-federated scheduling and reservation-based federated scheduling, that were developed to tackle resource waste in federated scheduling, and a stretching algorithm that also uses the tasks' graph structures. 

   more » « less
3. Enhancing outreach collections with live insects

   https://doi.org/10.3897/nhcm.2.148359  

   Herbison, Natalie (June 2025, Natural History Collections and Museomics)

   Outreach insect drawers serve as valuable educational tools, showcasing insect diversity and fostering curiosity. However, these static displays often fail to bridge the emotional gap between people and insects. Here, I discuss how by incorporating live insects, namely male bumble bees and carpenter bees, into outreach events might help to reduce fear and foster empathy amongst the public. I argue that, by integrating live insects with traditional displays, we can inspire deeper connections and encourage conservation efforts, ensuring that people see insects as living organisms worth protecting, rather than just specimens behind glass. Future research questions and suggestions regarding evaluation of outreach collections are discussed. 

   more » « less
4. Optimal Joint Offloading and Wireless Scheduling for Parallel Computing with Deadlines

   Qin, Xudong; Xu, Weijian; Li, Bin (June 2019, International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt))

   In this paper, we consider the problem of joint offloading and wireless scheduling design for parallel computing applications with hard deadlines. This is motivated by the rapid growth of compute-intensive mobile parallel computing applications (e.g., real-time video analysis, language translation) that require to be processed within a hard deadline. While there are many works on joint computing and communication algorithm design, most of them focused on the minimization of average computing time and may not be applicable for mobile applications with hard deadlines. In this work, we explicitly take hard deadlines for computing tasks into account and develop a joint offloading and scheduling algorithm based on the stochastic network optimization framework. The proposed algorithm is shown to achieve average energy consumption arbitrarily close to the optimal one. However, this algorithm involves a strong coupling between offloading and scheduling decisions, which yields significant challenges on its implementation. Towards this end, we first successfully decouple the offloading and scheduling decisions in the case with one time slot deadline by exploring the intrinsic structure of the proposed algorithm. Based on this, we further implement the proposed algorithm in the general setups. Simulations are provided to corroborate our findings. 

   more » « less
5. Improved Online Scheduling of Moldable Task Graphs under Common Speedup Models

   https://doi.org/10.1145/3630052  

   Perotin, Lucas; Sun, Hongyang (March 2024, ACM Transactions on Parallel Computing)

   We consider the online scheduling problem of moldable task graphs on multiprocessor systems for minimizing the overall completion time (or makespan). Moldable job scheduling has been widely studied in the literature, in particular when tasks have dependencies (i.e., task graphs) or when tasks are released on-the-fly (i.e., online). However, few studies have focused on both (i.e., online scheduling of moldable task graphs). In this article, we design a new online scheduling algorithm for this problem and derive constant competitive ratios under several common yet realistic speedup models (i.e., roofline, communication, Amdahl, and a general combination). These results improve the ones we have shown in the preliminary version of the article. We also prove, for each speedup model, a lower bound on the competitiveness of any online list scheduling algorithm that allocates processors to a task based only on the task’s parameters and not on its position in the graph. This lower bound matches exactly the competitive ratio of our algorithm for the roofline, communication, and Amdahl’s model, and is close to the ratio for the general model. Finally, we provide a lower bound on the competitive ratio of any deterministic online algorithm for the arbitrary speedup model, which is not constant but depends on the number of tasks in the longest path of the graph. 

   more » « less