{"entities":{"Q1097163":{"pageid":1107915,"ns":120,"title":"Item:Q1097163","lastrevid":66326421,"modified":"2026-04-12T09:19:29Z","type":"item","id":"Q1097163","labels":{"en":{"language":"en","value":"UET scheduling with unit interprocessor communication delays"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4033472"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$B36C0521-7E08-42D8-90FE-A70A7D6B97D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7139926ec50a4d087cce526524ee7498f52bc35","datavalue":{"value":{"text":"UET scheduling with unit interprocessor communication delays","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1097163$991D9A90-FE5C-49D8-95C3-54B9ED40E850","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed72a557adce3afcb7406fb74735f629d7c6efdf","datavalue":{"value":"0634.90031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$3BD49424-2310-4638-BCD9-93FCEAE10988","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6ef45f883167b0b479b2f10473184a865410491","datavalue":{"value":"10.1016/0166-218X(87)90042-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$3CFE3524-857A-4586-B6F8-A98C5EAF5276","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"221ce5358025bd49df98c029e677a03b185609ed","datavalue":{"value":{"entity-type":"item","numeric-id":1020037,"id":"Q1020037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$095F5822-3780-4339-B5CD-3BFA1025E01B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$CA297AFB-7806-4052-8F9C-170950154271","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1097163$6AA92E8A-BDD5-4E00-B979-CBC517BB1AD4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7d8ce85b11a414ea4e1bd493fc6ec0e6d756c80","datavalue":{"value":"We consider the problem of scheduling a partially ordered set of unit execution time tasks (UET) on \\(m>1\\) processors where there is a communication delay of unit time between any pair of distinct processors. We show that the problem of finding an optimal schedule is NP-hard. A greedy schedule is one where no processor remains idle if there is some task available which it could process. We establish that the length of an arbitrary greedy schedule, \\(\\omega^ c_ g\\) satisfies  \\[  \\omega^ c_ g\\leq (3-\\frac{2}{m})\\omega^ c_{opt}-(1-\\frac{1}{m})  \\]  where \\(\\omega^ c_{opt}\\) is the length of the optimal schedule. We define a generalized list schedule (a type of greedy schedule) and discuss anomalous behaviour of such schedules with respect to speed-up. The relevance of these results to the implementation of parallel languages is discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$D2AFA594-6EE8-4F2F-99EE-1BAD1E47F21B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$DA266766-3663-4FAA-8CC4-FA3E6E409F95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$D8A8A815-87F0-404F-889D-9C4FC36F5CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$654EF1FE-CF5C-4F20-AB82-86BD9FA6B2AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da6dd31530e122034b6a35d937708f1fffa876a9","datavalue":{"value":"4033472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$DAC5AEDA-47F8-49FD-BB85-1AEBD55AABF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ca28ab30649d1c505852fd4f8360d56305d88c6","datavalue":{"value":"UET scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$FA420A5C-9FCD-40AF-B14D-58CF8B191FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a450eb8041dd34d9143e4b21a5a645f9a163f82","datavalue":{"value":"list scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$60F7693C-0E3E-456F-A4E6-2C5E4645ECA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9895cc398f0b3081292d295ec24f160648cebfa","datavalue":{"value":"multiprocessor systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$F46DCB7C-2A59-4C4C-8FF2-6DA5371F1019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$12F8D42B-8B97-4339-8066-01D111AE8FA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c509eebda98b4edd879ae6b9026cdf7b9603835","datavalue":{"value":"speed-up anomaly","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$9922225A-FBAC-4A59-B0D6-C14A3221DB8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41951bd4e52da7e7313a895f05b32199a81ebb90","datavalue":{"value":"scheduling a partially ordered set of unit execution time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$A0615FBF-379B-402F-B501-F992CA54DFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf756bf561d2b0ef11cfcd3fe1a68c472508faf0","datavalue":{"value":"communication delay","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$CCF7E09B-4AAC-43F1-8473-0C4E8175A2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$0BE0B557-BA22-40F5-9917-F978800B4348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13ddd638f7d72180795ad0129118285cf94fc425","datavalue":{"value":"greedy schedule","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$368DD6D0-67BC-462E-8B50-C32C8972F869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af23de8ad196811fd3f020029e47fe49b1324d20","datavalue":{"value":"parallel languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1097163$3A7678FF-FD91-4FE3-9EDA-9240DADA102D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$66C692BE-4C4D-4C6F-B516-C366BDE32A5B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a7608d28af264e8cabf5bf3e4fb9fb3dd884c5b","datavalue":{"value":{"entity-type":"item","numeric-id":4181574,"id":"Q4181574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$F5A32C7A-9C19-4833-B06A-B33280FEE25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c1b2355b705a681cde4f391e4a3aee0c82cb98","datavalue":{"value":{"entity-type":"item","numeric-id":1104126,"id":"Q1104126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$92C33F1B-CCB5-46E1-B1F6-81742E4E7A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9661dc321e9197c44616cc21a898b0798188a31","datavalue":{"value":{"entity-type":"item","numeric-id":4131987,"id":"Q4131987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$0A3DE2F1-05AD-4B9B-B9C0-2C4114DC8937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d199017df4d3146f497fbc8db45c8d467a421d","datavalue":{"value":{"entity-type":"item","numeric-id":2556224,"id":"Q2556224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$654CCC9C-DCF3-4A61-844F-041EE73EB65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dbc9eeb518f4f28478120c423f894359ede433f","datavalue":{"value":{"entity-type":"item","numeric-id":3916360,"id":"Q3916360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$96ACDEB8-54B0-42AB-9FE1-8AE7CC47E12E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$DCAEF125-BD06-4948-8BEA-3DB233EA7B83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b993accea077add44db8e04f46a44e393ee057a0","datavalue":{"value":{"entity-type":"item","numeric-id":4152013,"id":"Q4152013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$709D9D9D-BD2A-46B8-9CB8-905021FDFEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d27fbad7eef42ac626d70629a585074b32100cb8","datavalue":{"value":{"entity-type":"item","numeric-id":3888526,"id":"Q3888526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$81BF0A32-0AD9-47DF-9E2C-203027BD219C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a089d2d23a33fbf3167ad429a459b6de513dd1","datavalue":{"value":{"entity-type":"item","numeric-id":1220386,"id":"Q1220386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1097163$D9EFA2F9-4104-4175-875D-CC25204E8014","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6b9ae099f4627bfb32ab0d70ef8ba7e7c137134","datavalue":{"value":"https://doi.org/10.1016/0166-218x(87)90042-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1097163$2C624D32-B36E-42B1-AF0E-53876FEB87EA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"49004fbd7f9dd79777fedff3e32927fefdbebaaf","datavalue":{"value":"W2078031780","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1097163$C4B2CA5E-E010-461A-91B4-E4A38DB9A767","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a04a50553a980fed1c4f7825b9c9054bfe3bacbc","datavalue":{"value":{"entity-type":"item","numeric-id":1860371,"id":"Q1860371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d99dd067b5c2213bfce046e6fb316802c5c88ff8","datavalue":{"value":{"amount":"+0.8480450510978699","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1097163$30AAAFF2-7C3C-4153-BD61-20E3DDF007A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14cd1e35849d302504b4b39cb1864cee10b9d273","datavalue":{"value":{"entity-type":"item","numeric-id":1292209,"id":"Q1292209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d99dd067b5c2213bfce046e6fb316802c5c88ff8","datavalue":{"value":{"amount":"+0.8480450510978699","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1097163$FF2B0DC5-7734-4795-923B-695DD12F99D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9694f12ef6bd9af53e97fe378edd0898e18791ad","datavalue":{"value":{"entity-type":"item","numeric-id":4843446,"id":"Q4843446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f600f50f607bd9ce17dd9d82ba10e9a83888568","datavalue":{"value":{"amount":"+0.8433076739311218","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1097163$08249F32-5E0F-40A3-AB6A-0B851F6F1A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45d68cfdba69979fe6277b189fc77894d3d572b3","datavalue":{"value":{"entity-type":"item","numeric-id":622602,"id":"Q622602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bed7fbda4d3175226f93b3aad52d81bde677b77","datavalue":{"value":{"amount":"+0.8343656063079834","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1097163$BC10DD46-F9B1-48D1-91C2-0D58992B6951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6cce2171dd52ed6511f6b9e7b60b12bffe26b58","datavalue":{"value":{"entity-type":"item","numeric-id":1342284,"id":"Q1342284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5861f88e07e748d3db12342ae0a00ab8c1fc730e","datavalue":{"value":{"amount":"+0.8327680826187134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1097163$4D417695-B1C1-419C-9F1D-7C34B2254593","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"UET scheduling with unit interprocessor communication delays","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/UET_scheduling_with_unit_interprocessor_communication_delays"}}}}}