{"entities":{"Q688237":{"pageid":690086,"ns":120,"title":"Item:Q688237","lastrevid":47202793,"modified":"2026-01-01T00:06:31Z","type":"item","id":"Q688237","labels":{"en":{"language":"en","value":"Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440384"}},"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":"Q688237$34B8D943-7F2E-4D41-ACCC-1C911DA0D5AF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd2e97b98a713917a38e7053083802579cee2a43","datavalue":{"value":{"text":"Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688237$773DF545-C7BA-4340-B9B5-BBC55F40F6BD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2e71b5d01abca60cfa0598114b20bd596a4cdbfe","datavalue":{"value":"0783.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688237$05EDF0C9-3D73-4771-9063-A43B626DC399","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d3b428a2db2a24ddcbc6dd24ea3338d608a6cda1","datavalue":{"value":"10.1016/0020-0190(93)90138-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688237$868B70F2-C459-4FE0-BA78-CE9FE70CAF0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb8112f391e48b28783318307853b48a4655e6fa","datavalue":{"value":{"entity-type":"item","numeric-id":586338,"id":"Q586338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$D80DEAA7-21CB-4157-8E43-18FC67E38B42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50f4b28ae4b329b8bd751ec7b7d1ed9d0078cff8","datavalue":{"value":{"entity-type":"item","numeric-id":586336,"id":"Q586336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$2258FAF2-AAD5-4773-AE90-4DE5148F1BE7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$8A687D7C-D84E-48F1-8D9F-63A302D761ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688237$8FB20341-72E3-44C4-AFAF-6115BCA70523","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f9fe27b82f0771f7724fc40039e9a2b75e3f68e","datavalue":{"value":"A \\(d\\)-dimensional reconfigurable mesh (denoted by \\(RM^ d)\\) consists of processors arranged as a \\(d\\)-dimensional mesh, in which each processor is connected to its neighbors via input/output ports. Each processor may also internally partition its ports so as to short-circuit all ports in each block of the partition. This partition may change during each step of the algorithm. The ability of each processor to short-circuit, or fuse, its ports allows the \\(RM^ d\\) to create various buses connecting processors.   We consider the simulation of a \\(P_ 0\\times P_ 1\\times\\cdots\\times P_{d-1}\\) \\(RM^ d\\) (where \\(P_{d-1} \\geq P_ 0\\), \\(P_ 1,\\ldots,P_{d-2})\\) by an \\(RM^ 2\\). \\textit{A. Schuster} [Dynamic reconfiguring networks for parallel computers: Algorithms and complexity bounds, Doctoral Dissertation, Dept. of Computer Science, Hebrew University, Israel (1991)] has shown that a step of any \\(RM^ d\\), for any constant \\(d>2\\), can be simulated by an \\(RM^ 2\\) in constant time. The simulation proposed in this paper is more efficient. We show that for constant \\(d\\), any \\(RM^ 2\\) that simulates a \\(P_ 0 \\times P_ 1 \\times \\cdots \\times P_{d-1}\\) \\(RM^ d\\) in constant time requires \\(\\Omega \\bigl( \\prod^{d-2}_{i=0}P^ 2_ i \\bigr)\\) processors. We give a method for simulating the above \\(RM^ d\\) in constant time on a \\(\\biggl( 2d \\prod^{d-1}_{i=1}P_ i \\times (2d+1) P_ 0+ \\sum^{d-2}_{i=1} \\prod^ i_{j=0}P_ j \\biggr)\\) \\(RM^ 2\\). If \\(P_ 0=\\Theta(P_{d- 1})\\), then this simulation uses an optimal number (to within a constant) of processors. If \\(d\\) is not a constant, then the simulation can be done on a \\(\\biggl( 4d \\prod^{d-1}_{i=1} P_ i \\times (2d+1)P_ 0+\\sum^{d-2}_{i=1} \\prod^ i_{j=0}P_ j \\biggr)\\) \\(RM^ 2\\). As an intermediate step, we give a two layer layout for a multidimensional mesh. We also show that an \\(RM^ 1\\) cannot simulate an arbitrary step of an \\(RM^ d\\) (where, \\(d \\geq 2)\\) in constant time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688237$C989F6EC-3077-4605-8FA4-5EBF6D7103B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688237$C846BFC9-7C82-4503-BB5F-38EB2B0736AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10b85655aba2fdb6347555277df2ffd39ea1a82a","datavalue":{"value":"94C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688237$044432CA-E98B-48C7-BB49-386925619334","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5ec79b2efb35b88ca47c8a71f1208fffa31a194","datavalue":{"value":"440384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688237$E28F5AE1-4101-44FE-8D2F-CFDAEFA4F1C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e53027033cae6fbc26744a05040eb76af38465e6","datavalue":{"value":"parallel computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q688237$C88F2095-15E8-4D67-8D54-06D4DB4F77DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22bf57f5dd7fd116d34a1a789bd1bf0b6d51d6a1","datavalue":{"value":"VLSI layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q688237$2E4D870F-0F7B-4BC1-A77A-B88E445D1AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38e75ac8706b9e8cafc5ffd5f6dcf371cf2e0dfe","datavalue":{"value":"reconfigurable mesh","type":"string"},"datatype":"string"},"type":"statement","id":"Q688237$47286BE4-29B8-4CB9-874A-A5CAFC4DC04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f828563fee5a57e5f16da87a79378ac587cea3ac","datavalue":{"value":"simulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q688237$DCE87E7B-9A98-4105-B68D-EE62F901AF88","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":"Q688237$E36923BD-BEDF-467D-BE11-6784726C4324","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb44e08a53e4c007a1970cc14d1cf388b1586e9","datavalue":{"value":{"entity-type":"item","numeric-id":4710686,"id":"Q4710686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$2B33ECAF-8751-4D2C-B5C3-F3E2E2516317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c44cd24cdd8fa39cc0df3ef3b6dc0e82d41992","datavalue":{"value":{"entity-type":"item","numeric-id":4036559,"id":"Q4036559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$B92DD3E0-C369-4B9F-B54F-F967375741D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b578d56855c1de2e2f897c61ed2ff7168e6c3325","datavalue":{"value":{"entity-type":"item","numeric-id":4002466,"id":"Q4002466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$F70162AF-996E-44FB-B0AC-0902693F609A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a364102957519556bae7af69f7dbcf14a3064d59","datavalue":{"value":{"entity-type":"item","numeric-id":1183475,"id":"Q1183475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$05F0A971-B77B-4BFF-877A-7E423E482B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"936ff4169b278a4a035b993706fc829037c91fbe","datavalue":{"value":{"entity-type":"item","numeric-id":4181968,"id":"Q4181968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$25EE02A3-7902-4464-969A-69E8E31BAC86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d655f5ffaeb73d580c712f684eb7ddf7754b1bef","datavalue":{"value":{"entity-type":"item","numeric-id":916359,"id":"Q916359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688237$02FABB61-CF7B-4FDA-8C40-4B9529D9EC13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"424260e3944d0d24ccc92536fe31c73b88dbab76","datavalue":{"value":{"entity-type":"item","numeric-id":3806840,"id":"Q3806840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82c3f8585a8794d2eac92ecdf46939f2b65dd8af","datavalue":{"value":{"amount":"+0.8270440697669983","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":"Q688237$02BE6D37-D8E9-498B-913F-E44F30F22CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3950f797cfbd1a48c98cea6647a3ce482255f49","datavalue":{"value":{"entity-type":"item","numeric-id":672023,"id":"Q672023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db8c70dbdc1c40b9ae845ad27b584b2b4152c4ad","datavalue":{"value":{"amount":"+0.7994401454925537","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":"Q688237$1D867688-AD87-441D-96C8-BEDD73565F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c32e15148a855fc27f7322b6f810fc6d1722e152","datavalue":{"value":{"entity-type":"item","numeric-id":2433307,"id":"Q2433307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aeee6f1bfae073d3d2a0621ebadaac5ff5b2c34","datavalue":{"value":{"amount":"+0.7900248169898987","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":"Q688237$AAF99DD6-1FBF-40D3-829F-044308BD31A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b125257b2df32ead8491664b45aca24e2870385","datavalue":{"value":{"entity-type":"item","numeric-id":1878709,"id":"Q1878709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e2dfc0fb1c440f115844943fbcb72e3107a6da4","datavalue":{"value":{"amount":"+0.7863011360168457","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":"Q688237$F8B24FDB-310A-4BC3-9629-9BB42BB76855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea05f5b32af8a185895d8c09adb9139ce24abafd","datavalue":{"value":{"entity-type":"item","numeric-id":3979258,"id":"Q3979258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16cd737d45e379e9c4d38d029422097277e2a4c5","datavalue":{"value":{"amount":"+0.7810121178627014","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":"Q688237$34B9B65B-7574-4D15-8B02-847A8FA7EAE0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:688237","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:688237"}}}}}