Large-Scale Fork-Join Networks with Synchronization Constraints

具有同步约束的大规模分叉连接网络

• 批准号: 1538149
• 负责人: Guodong Pang
• 金额: $ 25万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1538149&HistoricalAwards=false
• 关键词: Large; Scale; Fork; Join; Networks

Fork-join networks with synchronization constraints can be widely used to model patient flows in hospitals (e.g., emergency department treatment and patient discharge process) and data centers (e.g., parallelized Web search), among many other applications. In such networks, jobs are forked into parallel tasks to be served at service stations with parallel servers, and tasks are then joined for job completion or further processing provided that certain synchronization constraints are satisfied, for example, only completed tasks from the same job can be joined (non-exchangeable). However, very little is known about the performance, reliability and control of these networks, and existing methods in stochastic networks cannot be applied to study them. This award supports development of new methodology to better understand important performance measures (e.g., congestions and response times) of fork-join networks with non-exchangeable synchronization constraints, to design reliable fork-join networks with synchronization constraints operating in dynamic random environments, and to manage them in a cost-effective way. The research findings will have a broad impact on the society by improving the efficiency and quality of services in healthcare and data centers. The research will result in young STEM-trained graduates and underrepresented groups with new mathematical tools that help understand and improve the delivered services. The main mathematical challenge to study fork-join networks of multi-server service stations with non-exchangeable synchronization lies in the resequencing of arrival orders after service completion at each station due to randomness of service times. Unlike classical queueing networks, delay for synchronization is a key performance measure affecting system congestion, while resequencing is its determining factor. No analytical methods and results are known for such networks. This research will develop a new framework to solve the resequencing problem in fork-join networks, and thus, result in effective approximations for the synchronization dynamics as well as the service dynamics. The approach will use multi-parameter stochastic processes to study the service, queueing and synchronization dynamics, including sequential empirical processes driven by random vectors and their limits, and two-parameter processes tracking elapsed and residual service and wait times. Coordination and information sharing among parallel tasks of each job during their services will be exploited to develop optimal control policies for fork-join networks with synchronization constraints in order to minimize delay for synchronization as well as delay for service. Preventive strategies will be provided on the design and management of reliable fork-join networks with synchronization constraints operating in dynamic random environments.

具有同步约束的Fork-join网络可以广泛用于对医院中的患者流进行建模（例如，急诊室治疗和患者出院流程）和数据中心（例如，并行Web搜索），以及许多其他应用程序。 在这样的网络中，作业被分叉成并行任务，以在具有并行服务器的服务站处被服务，并且任务然后被加入以用于作业完成或进一步处理，只要满足某些同步约束，例如，仅来自相同作业的已完成的任务可以被加入（不可交换）。 然而，很少有人知道这些网络的性能，可靠性和控制，现有的方法在随机网络不能应用于研究它们。该奖项支持开发新的方法，以更好地了解重要的绩效指标（例如，的fork-join网络的不可交换的同步约束的同步时间和响应时间），设计可靠的fork-join网络的同步约束运行在动态随机环境中，并管理它们在一个具有成本效益的方式。研究结果将通过提高医疗保健和数据中心的服务效率和质量对社会产生广泛影响。这项研究将为年轻的STEM毕业生和代表性不足的群体提供新的数学工具，帮助理解和改善所提供的服务。研究具有不可交换同步的多服务器服务站fork-join网络的主要数学挑战在于，由于服务时间的随机性，在每个服务站完成服务后到达订单的重新排序。与传统的同步网络不同，同步延迟是影响系统拥塞的关键性能指标，而重排序则是其决定性因素。没有分析方法和结果是已知的，这样的网络。这项研究将开发一个新的框架来解决fork-join网络中的重排序问题，从而有效地近似同步动态以及服务动态。该方法将使用多参数随机过程来研究服务，排队和同步动态，包括随机向量及其限制驱动的顺序经验过程，以及跟踪已过和剩余服务和等待时间的双参数过程。利用每个作业的并行任务在其服务期间的协调和信息共享，为具有同步约束的fork-join网络开发最优控制策略，以最小化同步延迟以及服务延迟。将提供预防策略的设计和管理的可靠的fork-join网络的同步约束运行在动态随机环境中。